23
$\begingroup$

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?

$\endgroup$
28
$\begingroup$

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.

bad example for just rotating

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)$.

bad example continued

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$.

splaying the bad example

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.

$\endgroup$
  • $\begingroup$ I think the rotations algorithms are exactly the same, mine is simply shorter and more understandable. Rather than looking at grandparents I only consider parent in one rotating step. Doesnt it make precisely the same outcome? $\endgroup$ – Bober02 Apr 11 '12 at 22:58
  • $\begingroup$ I guess you might be referring to two SPLAYING algos, one top down, the other bottom up, and not mine, is that correct? I was referring to my algo vs bottom up splaying $\endgroup$ – Bober02 Apr 11 '12 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.