Self-adjusting binary trees that work in $O(\log n)$ amortized time bound. The operation performed is the splay operation.

For a splay operation at node x: ($p(x)$ is the parent of $x$)

• Case (a): If $x$ has a parent but no grandparent we rotate at $p(x)$.
• Case (b): If $x$ has a grandparent and both $x$ and $p(x)$ are both left or right childrenn, we rotate at $p^2(x)$ and then at $p(x)$.
• Case (c): If $x$ has a grandparent and $x$ is a left and $p(x)$ is a right child, or vice versa, we rotate at $p(x)$ and then at the new parent of $x$.

This moves $x$ to the root of the tree while rearranging the rest of the original path to $x$.

We perform a splay operation during each access or update operation. Using amortized time analysis for $m$ operations total time taken is $O(m\log n)$ or $O(\log n)$ amortized time per operation.

Amortized Time Analysis

Let $T$ be a tree of $n$ nodes. For node $v\in T$ let $n_T(v)$ ve the number of nodes in the subtree of $v$ including $v$.

We define the potential function $\phi(T)=\sum_{v\in T}r_T(v)$ where $r_{T}(v)=\log {2}\lfloor n{T}(v)\rfloor$.

For a completely skewed tree it will be $\log_2n+\log_2(n-1)+\ldots \log_21=O(n\log n)$.

For a completely balanced tree of height $h$ it will be $\sum_{i=0}^h2^i\log_2(2^{h-i+1})=\sum_{i=0}^h2^i(h-i+1)=O(n)$

Suppose the tree undergoes $m$ searches for keys $k_{i_1},k_{i_2},\ldots k_{i_m}$ starting from tree $T_0$ and after searching for $k_{i_1}$ to $T_1$ and so on until $T_m$.

Let actual cost of $i^{\rm th}$ search be $c_i$ and amortized cost of $i^{\rm th}$ search be $\hat c_i=c_i+\phi(T_i)-\phi(T_{i-1})$. We claim that $\hat{c}_{i} \leqslant 3 \log _{2} n$. Hence actual cost becomes \(\begin{align} \sum_{i=1}^mc_i&=\sum_{i=1}^m[\hat c_i+\phi(T_{i-1})-\phi(T_i)]\\ &=\sum_{i=1}^m\hat c_i+\sum_{i=1}^m(\phi(T_{i-1}-\phi(T_i)))\\ &=\sum_{i=1}^m\hat c_i+[\phi(T_0)-\phi(T_m)]\\ &=\sum_{i=1}^m\hat c_i+n\log n\\ &\le3m\log n+n\log n\\ &\le 4m\log n\tag{$m\ge n$} \end{align}\)

Now we prove $\hat{c}_{i} \leqslant 3 \log _{2} n$ for various cases. $r’$ represents the rank after rotation.

Lemma If $a+b\le c$ then $\log a+\log b\le 2\log c-2$ since $ab\le c^2/4$ where $c^2\ge (a+b)^2\ge 4ab$ using AM-GM inequality.

Case (a) (zig)

Total cost involves 1 rotation and potential change. We have $r’(x)=r(y)$ so $\Delta \phi=(r’(x)+r’(y))-(r(x)+r(y))=r’(y)-r(x)\le r’(x)-r(x)$ as $y$ has less nodes afterwards and less rank. So $\hat c_i\le 1+(r’(x)-r(x))\le 1+3(r’(x)-r(x))$

Case (c) (zig-zag)

Total cost involves 2 rotation and potential change $\Delta \phi=r’(x)+r’(y)+r’(z)-r(x)-r(y)-r(z)$

Here $\hat c_i=2+(r’(x)-r(x))+r’(y)+r’(z)-r(y)-r(z)$

Also $n’(y)+n’(z)= n’(x)-1\le n’(x)$. Using the lemma $\log (n’(y)) + \log (n’(z))\le 2\log (n’(x))-2$ or $r’(y)+r’(z)\le 2r’(x)-2$.

So we have $\hat c_i\le 2+ (r’(x)-r(x))+(2r’(x)-2)-r(y)-r(z)$ or $\hat c_i\le (3r’(x)-r(x)-r(y)-r(z)$. Also we have $r(z)=r(x)$ and $r(y)\ge r(x)$ so $\hat c_i\le 3(r’(x)-r(x))$

Case (b) (zig-zig)

Total cost involves 2 rotation and potential change

Similar to case (c) we have $\hat c_i=2+(r’(x)-r(x))+r’(y)+r’(z)-r(y)-r(z)$ and $n(x)+n’(z)+1=n’(x)$ giving $r(x)+r’(z)\le 2r’(x)-2$ or $r’(z)\le 2r’(x)-r(x)-2$

So we have $\hat c_i\le 2+(r’(x)-r(x))+r’(y)+(2r’(x)-r(x)-2)-r(y)-r(z)$ or $\hat c_i\le (3r’(x)-2r(x))+r’(y)-r(y)-r(z)$. Also we have $r(z)=r’(x)$ and $r(y)\ge r(x) $ giving $\hat c_i\le 3(r’(x)-r(x))-\underbrace{(r(z)-r’(y))}_{>0}\ge 3(r’(x)-r(x))$

Conclusion

If we have $d$ splays then $\hat c=\sum_{i=1}^d\hat c_i\le \sum_{i=1}^d3(r_i(x)-r_{i-1}(x))=3(r_d(x)-r_0(x))$

The maximum change in rank can be $\log n$ giving $\hat c\le 3\log n$