Rice University - Comp 212 - Intermediate Programming

Spring 2003

Lecture 32 - Splay Trees

Review: Comparing the four IDictionary implementations

		Expected-case Cost	Worst-case Cost

	lookup()	O(n)	O(n)
DictLRS	insert()	O(n)	O(n)
	remove()	O(n)	O(n)

	lookup()	O(log n)	O(n)
DictBT	insert()	O(log n)	O(n)
	remove()	O(log n)	O(n)

	lookup()	O(log n)	O(log n)
DictArray	insert()	O(n)	O(n)
	remove()	O(n)	O(n)

	lookup()	O(1)	O(n)
DictHash	insert()	O(1)	O(n)
	remove()	O(1)	O(n)

DictHash is an excellent implementation of IDictionary.

Hash tables are, however, a poor choice for ranged operations, such as IRangeDictionary's removeRange.

How can we improve the performance of binary search trees?

Given any set of keys, there are many possible binary search trees.

These binary search trees can be perfectly balanced.

The same keys might be arranged to form a ``perfectly'' unbalanced tree.

What can we do to "fix" unbalanced trees?

Rotation

Rotation preserves the binary search tree property.

A Single Rotation Applied

A single left rotation on the original root (``3'') of the tree produces:

Multiple Rotations Applied

Performing a left rotation on alternating nodes (``3'', ``22'', and ``41'') of the original tree produces:

A Visitor for Rotation on a BiTree

/**
* Returns the subtree of the host with the min value in the root
* if the tree is not empty, otherwise returns the host itself.
* @author Alan Cox
*/
public class RotateLeft implements IVisitor {
public final static RotateLeft Singleton = new RotateLeft();

private RotateLeft() {
}

    /**
     * Trivial
     * @param host satisfies the binary search tree property.
     * @param input == null, not used.
     * @return host
     */
    public Object emptyCase(BiTree host, Object input) {
        throw new IllegalStateException("Can't rotate an empty tree.");
    }

    /**
     * @param host satisfies the binary search tree property.
     * @param input == null, not used.
     * @return subtree with minimum root.
     */
    public Object nonEmptyCase(BiTree host, Object input) {
        BiTree right = host.getRightSubTree();
        host.setRightSubTree(right.getLeftSubTree());
        right.setLeftSubTree(host);
        return right;
    }
}

Top-down Splay

Top-down splay is an operation, like BSTFinder, on a binary search tree. It differs from BSTFinder in that it restructures the tree as it descends toward the desired key's place in the tree. During descent, ...

long "straight" paths are shortened by rotation. For example, if the desired key is greater than both the current node's key and its right child's key, a left rotation is performed.
all nodes are removed from the original tree and reinserted in one of two new trees built from scratch (i.e., initially empty). One of these new trees contains all elements less than the desired key and the other contains all elements greater than the desired key. Let's call them "new left" and "new right".

This sounds hard and costly, but isn't. We'll see why later.

Ultimately, if we find the desired key, we reassemble the binary search tree making the desired key's node the new root with "new left" as its left subtree and "new right" as its right subtree.

If the desired key is not found, the next smaller or next larger key is made the new root.

The algorithm is simple. The performance proof is hard.

Tarjan and Sleator proved that a sequence of n splay operations on a tree of n nodes would take O(n log n) time.

Any individual splay operation (taken in isolation) may take O(n) time; but the extra work done for that splay operation will make future splay operations cheaper.

The traditional dictionary operations, i.e., lookup, insert, and remove, can be reimplemented using top-down splay as a helper.

There is little work for lookup, insert, and remove to do; the hard work is done by splay.

Top-down Splay Pseudo-code

splay(Comparable key, BiTree root) returns BiTree
{
dummy is an empty BiTree;
BiTree lefttreemax, righttreemin, child;

        lefttreemax = righttreemin = dummy;
        for (;; root = child) {
                if (key < root.key) {
                        if ((child = root.getleft()) is empty)
                                break;
                        if (key < child.key) {
                                Rotate right.
                                root = child;
                                if ((child = root.getleft()) is empty)
                                        break;
                        }
                        /* Link into the new root's right tree. */
                        righttreemin.setleft(root);
                        righttreemin = root;
                } else if (key > root.key) {
                        if ((child = root.getright()) is empty)
                                break;
                        if (key > child.key) {
                                Rotate left.
                                root = child;
                                if ((child = root.getright()) is empty)
                                        break;
                        }
                        /* Link into the new root's left tree. */
                        lefttreemax.setright(root);
                        lefttreemax = root;
                } else
                        break;
        }
        /* Assemble the new root. */
        lefttreemax.setright(root.getleft());
        righttreemin.setleft(root.getright());
        root.setleft(dummy.getright());
        root.setright(dummy.getleft());
        return (root);
}

Splay Tree Demo

Sleator has an on-line demo at http://www.link.cs.cmu.edu/splay/