[Solved]: Splay tree with odd number of rotations

Problem Detail: 

When inserting an item into a splay tree, rotations are performed in pairs based on either a zig-zag or zig-zig pattern. When there is an odd number of rotations to be performed, one could either do the extra rotation beginning at the leaf or save the extra rotation and do it at the root. Does it matter?

For example, in the attached image I insert a 4 into a BST, and "splay it" it to the root. On the top of the figure, I first locate the zig-zig pair at the leaf node and perform the zig-zag splay from the bottom leaving a final right rotation at the root. At the bottom of the figure, I first do the odd rotation starting from the leaf, and the then do a zig-zig splay to the root.

Which is correct? Or will both lead to the usual splay-tree performance?

Asked By : wcochran

Answered By : A.Schulz

It really does not matter for the analysis. The key lemma for analyzing the splay-tree performance is the access lemma. It states that the amortized costs of a splay(x) operation is less than $1+3(r(t)-r(x))$, where $t$ is the root of the tree and $r(u):=\lfloor \log (\text{weight of $u$'s subtree}) \rfloor$. The weight of a subtree is the sum of the weights of its nodes. (Weights (positive) will be picked depending on the application of the lemma.) The potential function used is $\Phi(T)=\sum_{x \text{ node of } T} r(t)$.

The proof of the access lemma looks at the costs of a single zig/zig-zag/zig-zig etc. operation. You get

1. Costs of a zig or zag operations are $1+3(r_+(u) - r(u))$, where $r_+$ is the rang after the operation and $u$ is the node rotated upwards.

2. Costs of zig-zig /zig-zag and symmetric operations are $3(r_+(u) - r(u))$.

If you add these differences up for the operations performed in a single splay(x), you get a telescope sum and what remains is $1+3(r(t)-r(x))$.

If you change the order of the rotations you will get the same sum. The only difference is that now the ''+1'' comes from the first rotation and not from the last rotation. You could even do the zig rotation in the middle. All further (classical) analysis relies on the access lemma.

However, the reason why you perform the single rotation last, is that you do not know if the depth of the node is even or odd in advance.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14200