Análisis

Note que todas las operaciones del árbol tienen un costo proporcional a la operación $splay$ que las sigue. Por lo tanto, podemos concentrarnos en el costo de esta operación (si bien luego consideraremos la modificación que hacen en el árbol la inserción y el borrado).

Para analizar esta operación en forma amortizada definiremos una función potencial. Sea $S_i(x)$ el subárbol con raíz $x$ luego de la operación $i$, y sea $s_i(x) = |S_i(x)|$ su número de nodos. Finalmente, sea $r_i(x) = \log_2 s_i(x)$ el rango de $x$ luego de la operación $i$. La función potencial del árbol $T$, visto como un conjunto de nodos, es entonces

$$\phi_i ~~=~~ \sum_{x \in T} r_i(x).$$

Analicemos cómo cambia $\Delta\phi_i$ luego de realizar las rotaciones.

Zig-zig y zag-zag

Los únicos nodos cuyos rangos se modifican son los de $x$, $y$, y $z$. Por lo tanto,

$$\Delta\phi_i ~~=~~ (r_i(x)-r_{i-1}(x)) + (r_i(y)-r_{i-1}(y)) + (r_i(z)-r_{i-1}(z)).$$

Note también los siguientes hechos simples: (1) $r_i(x) = r_{i-1}(z)$; (2) $r_{i-1}(y) \ge r_{i-1}(x)$; (3) $r_i(y) \le r_i(x)$. El costo real de hacer un zig-zig es $c_i=2$, mientras que el costo amortizado es

$$\begin{array}{c c c} \hat{c_i} ~~=~~ c_i + \Delta\phi_i &=& 2 + (r_i(x)-r_{i-1}(x)) + (r_i(y)-r_{i-1}(y)) + (r_i(z)-r_{i-1}(z))\\ & = & 2 + [r_i(x)-r_{i-1}(z)] + r_i(y) + r_i(z) - r_{i-1}(x) - r_{i-1}(y)\\ & \le & 2 + r_i(x) + r_i(z) - r_{i-1}(x) - r_{i-1}(x) \\ & = & 2 + r_i(x) + r_i(z) - 2 r_{i-1}(x), \end{array}$$

donde en la desigualdad usamos los tres hechos simples mencionados.

Vamos a usar la siguiente propiedad, que se deduce de la concavidad del logaritmo, pero igual mostramos su deducción:

$$\begin{array}{c c c} 0 & \le & (a-b)^2, \\ 2ab & \le & a^2 + b^2, \\ 4ab & \le & (a+b)^2, \\ \log_2(4ab) & \le & \log_2((a+b)^2), \\ \log_2(ab) & \le & 2\log_2(a+b)-2, \\ \log_2 a + \log_2 b & \le & 2\log_2(a+b)-2. \\ \end{array}$$

Usaremos esta propiedad y el hecho simple de que $s_{i-1}(x)+s_i(z) \le s_i(x)$ para obtener lo siguiente:

$$\begin{array}{c c c} r_{i-1}(x) + r_i(z) &=& \log_2 s_{i-1}(x) + \log_2 s_i(z) ~~\le~~ 2\log_2 (s_{i-1}(x)+s_i(z))-2 \\ &\le & 2\log_2 s_i(x) - 2 ~~=~~ 2 r_i(x)-2. \end{array}$$

Por lo tanto, podemos reemplazar $r_i(z)$ por $2r_i(x)-r_{i-1}(x)-2$ en nuestra ecuación de $\hat{c_i}$ para obtener

$$\hat{c_i} ~~\le~~ 3(r_i(x)-r_{i-1}(x)).$$

Zig-zag y zag-zig

Partimos de la misma forma que antes y luego acotamos:

$$\begin{array}{c c c} \hat{c_i} ~~=~~ c_i + \Delta\phi_i &=& 2 + (r_i(x)-r_{i-1}(x)) + (r_i(y)-r_{i-1}(y)) + (r_i(z)-r_{i-1}(z))\\ & = & 2 + [r_i(x)-r_{i-1}(z)] + r_i(y) + r_i(z) - r_{i-1}(x) - r_{i-1}(y)\\ & \le & 2 + r_i(y) + r_i(z) - 2r_{i-1}(x), \end{array}$$

donde en la desigualdad usamos que $r_i(x)=r_{i-1}(z)$ y que $r_{i-1}(y) \ge r_{i-1}(x)$. Ahora volvemos a usar que $\log_2 a + \log_2 b \le 2\log_2(a+b)-2$ y que $s_i(y) + s_i(z) \le s_i(x)$ para acotar

$$\begin{array}{c c c} r_i(y) + r_i(z) & = & \log_2 s_i(y) + \log_2 s_i(z) ~~\le~~ 2\log_2 (s_i(y)+s_i(z))-2 \\ & \le & 2\log_2 s_i(x) - 2 ~~=~~ 2r_i(x) - 2. \end{array}$$

Sustituyendo en la fórmula de $\hat{c_i}$ tenemos entonces

$$\hat{c_i} ~~\le~~ 2(r_i(x)-r_{i-1}(x)) ~~\le~~ 3(r_i(x)-r_{i-1}(x))$$

Zig y zag

En estas operaciones tenemos $c_i=1$. Como $r_i(y) \le r_{i-1}(y)$ y $r_i(x) \ge r_{i-1}(x)$,

$$\begin{array}{c c c} \hat{c_i} &=& c_i + (r_i(x)-r_{i-1}(x)) + (r_i(y)-r_{i-1}(y)) \\ & \le & 1 + r_i(x) - r_{i-1}(x) \\ & \le & 1 + 3(r_i(x) - r_{i-1}(x)). \end{array}$$

Splay

Una operación $splay$ se compone de una secuencia de $m$ rotaciones dobles consecutivas, posiblemente terminadas por una simple, todas aplicadas sobre el mismo nodo $x$. Su costo amortizado es entonces

$$\hat{c} ~~\le~~ 1 + \sum_{i=1}^m 3(r_i(x)-r_{i-1}(x)) ~~=~~ 1+3(r_m(x)-r_0(x)) ~~\le~~ 1+3\log_2 n$$

donde la última desigualdad se obtiene notando que $r_m(x)=\log_2 n$ porque $x$ termina siendo la raíz, y despreciando $r_0(x) \ge 0$.

Operaciones del árbol

La cota de splay implica directamente una cota amortizada de $O(\log n)$ para las operaciones de búsqueda exitosa sobre un splay tree. Lo mismo ocurre con la búsqueda infructuosa, la inserción y el borrado, ya que hemos hecho que su costo sea proporcional a la operación de splay correspondiente. La única consideración final que necesitamos es que la inserción, al agregar un elemento $x$, puede incrementar el potencial $\phi$, lo cual debe ser absorbido por el costo amortizado de la inserción. La diferencia de potencial que produce la inserción de una hoja $x$, siendo $y_1,\ldots,y_m$ los nodos de su camino hacia la raíz y $s(y_j)$ sus tamaños, son

$$\begin{array}{c c c} \Delta\phi & = & \sum_{j=1}^m (\log_2 (s(y_j)+1) - \log_2 s(y_j)) \\ & \le & (\log_2(s(y_m)+1) - \log_2 s(y_m)) + \sum_{j=1}^{m-1} (\log_2 s(y_{j+1}) - \log_2 s(y_j)) \\ & = & \log_2(s(y_m)+1) - \log_2 s(y_m) + \log_2 s(y_m) - \log_2 s(y_1) \\ & \le & \log_2 (n+1) - 1 \\ & \le & \log_2 n, \end{array}$$

donde usamos que, como $y_{j+1}$ es el padre de $y_j$, debe valer $s(y_{j+1}) \ge s(y_j)+1$. El incremento de potencial de la inserción es también $O(\log n)$, lo que completa el análisis.