# Spring 2007

## Lecture 34 - 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)
• DictHash is an excellent implementation of IDictionary.
• Hash tables are, however, a poor choice for ranged operations, such as IRangeDictionary defined in the following:
```	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?

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

### Red-Black Tree

Lecture note in PDF format

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