Why does the splay tree rotation algorithm take into account both the parent and grandparent node?

Problem Detail: 

I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why would the following not work:

As we insert, for instance, a new node to the tree, we check whether we insert into the left or right subtree. If we insert into the left, we rotate the result RIGHT, and vice versa for right subtree. Recursively it would be sth like this

Tree insert(Tree root, Key k){     if(k < root.key){         root.setLeft(insert(root.getLeft(), key);         return rotateRight(root);     }     //vice versa for right subtree } 

That should avoid the whole "splay" procedure, don't you think?

Asked By : Bober02

Answered By : JeffE

The simpler balancing algorithm can require $\Omega(n)$ amortized time per rotation in the worst case. Suppose the tree is just a totally unbalanced path of right children; no node has a left child. The only leaf in this tree is the tree with the maximum key. If you rotate this step by step up to the root, you've used $n-1$ rotations, and the resulting tree is still totally unbalanced.

Now suppose we repeatedly promote every node in the tree, one at a time, in decreasing key order, using the simpler algorithm. After all the promotions are done, the tree has returned to its original state, and we have used roughly $n^2/2$ rotations. Thus, on average, each promotion in this sequence requires $\Omega(n)$ rotations; moreover, I can repeat this pattern forever. So the amortized cost for this promotion algorithm is $\Omega(n)$.

This bad example appears in Sleator and Tarjan's original splay tree paper.

The splay algorithm considers not just one node at a time, but two nodes at a time. In particular, if the node $x$ being splayed is the right child of a right child, the splay algorithm first rotates $x$'s parent, and only then rotates $x$.

The advantage of this more complex algorithm is that it not only brings the accessed node to the root, but also moves every ancestor of the accessed node roughly halfway to the root, but never moves any node more than a constant number of levels away from the root.

Sleator and Tarjan prove that the amortized time per splay is only $O(\log n)$. (The proof uses a tedious case analysis using a magic potential function; honestly, if you're curious, just read the original paper.) Of course a single splay can take $\Omega(n)$ time, but starting with an empty tree, you have to perform a lot of insertions and splays to set up such a bad example.

More briefly: Splaying moves nodes upward quickly and downward slowly.

Best Answer from StackOverflow

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