Rice University - Comp 212 - Intermediate Programming

Spring 2006

Lecture 36 - Balancing Binary Trees: Red-Black Trees and 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)
	public interface IRangeDictionary extends IDictionary {
    		/**
     		* Removes every DictionaryPair with a key greater than or equal
     		* to keyLo and less than or equal to keyHi.  Returns an IList
     		* of DictionaryPairs removed.  Throws an exception if keyLo is
     		* greater than keyHi.
     		*/
    		public IList removeRange(Comparable keyLo, Comparable keyHi);
    		/**
     		* Looks up every DictionaryPair with a key greater than or equal
     		* to keyLo and less than or equal to keyHi.  Returns an IList
     		* of all such DictionaryPairs.  Throws an exception if keyLo is
     		* greater than keyHi.
     		*/
    		public IList lookupRange(Comparable keyLo, Comparable keyHi);
	}




How can we improve the performance of binary search trees?


Rotation



A Single Rotation Applied



Multiple Rotations Applied



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;
    }
}


Red-Black Tree

Lecture note in PDF format


Top-down 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);
}

Click here for the full code

 


Splay Tree Demo