# 证明伸展树与动态树的时间复杂度

#### Splay时间复杂度证明

###### 证明.

$2\lg(x)-\lg(y)-\lg(z)$
$=\lg((y+z+1)^2)-\lg(y)-\lg(z)$
$=\lg(\frac{(y+z+1)^2}{yz})$
$=\lg(\frac{2yz}{yz}+\frac{y^2+z^2+1+2y+2z}{yz})$
$\geq \lg(2+\frac{y}{z}+\frac{z}{y})$
$\geq \lg(2+2)$
$=2$

###### 证明.

$r'(x)+r'(y)+r'(z)-r(x)-r(y)-r(z)$
$=r'(y)+r'(z)-r(x)-r(y)$
$\leq r'(x)+r'(z)-2r(x)$ 由于$size'(x)=size(x)+size'(z)+1$,根据定理0,加上2r'(x)-r'(z)-r(x)-2。
$\leq 3(r'(x)+r(x))-2$

$r'(x)+r'(y)+r'(z)-r(x)-r(y)-r(z)$
$=r'(y)+r'(z)-r(x)-r(y)$
$\leq r'(y)+r'(z)-2r(x)$,由于size'(x)=size'(y)+size'(z)+1,根据定理0,加上2r'(x)-r'(y)-r'(z)-2
$\leq 2(r'(x)-r(x))-2$

### 1 thought on “证明伸展树与动态树的时间复杂度”

1. Thanks for all your valuable hard work on this site. Gloria enjoys conducting investigations and it’s obvious why. My spouse and i know all about the powerful tactic you render practical guides via the blog and as well as boost contribution from people on this topic and my child is without question discovering a lot. Take advantage of the remaining portion of the new year. You have been carrying out a stunning job.