Balancing trees

As we have seen in the previous section, if we just let the tree grow, consecutive inserts and/or deletes may result in a highly unbalanced tree, large height, and consequently very poor performance. Ideally, we would like a tree with \(O(\log n)\) height. Thus, we would like to change the “shape” of the tree but keep in mind that we have to retain the order of elements (smaller on the left, bigger on the right). There are basically three approaches to do this:

Rotations

Idea: Rotation is a very local change of a few pointers that lifts one subtree and lowers the other while preserving order of the nodes.

Used in: AVL tree, Red-black tree, AA tree, Treap, Splay tree

Tip: Check the “show order” box and notice that rotations don’t change the (in-order) order of nodes. Check the “show subtrees” box and notice how the height of individual subtrees changes.

Exercise 1: Play around with the applet until you get the hang of rotations. Using only rotations, transform any randomly generated tree into a linear chain where all nodes (except the leaf) have only the right son.

Exercise 2: Using only rotations transform the left tree into the right one:

How would you transform the right tree into the left one?

Exercise 3: Prove that any BST (with n nodes) can be transformed into any other BST (with the same elements). How many rotations are sufficient? (Can you also prove some lower bound?)

Rotations explained

Let $a$ and $b$ be two neighbouring nodes and let $\alpha, \beta, \gamma$ represent the subtrees as in the figure below (the subtrees may be arbitrary, possibly even empty).
An operation that transforms the left subtree into the right subtree in the figure below is called rotation at $a$ or right rotation. Similarly, an operation which transforms the right subtree into the left one is called rotation at $b$ or left rotation.



Note that

  1. the order of elements is preserved: $\alpha < a < \beta < b < \gamma$, in other words, the in-order words, the in-order traversals of both trees are the same
  2. the change is local: only 3 pointers for the left / right children (and possibly 3 parent pointers) are changed (the bold edges in the figure above)
  3. subtree $\alpha$ is raised, subtree $\beta$ stays at the same level and subtree $\gamma$ drops one level; in particular, if subtree $\alpha$ is higher than $\beta$ and $\gamma$, the the overall height of the whole subtree is decreased by right rotation (similarly for $\gamma$ and left rotation)
  4. left and right rotations are inverse operations

Exercise 4: Implement rotations in your favourite language. (Beware of the special cases: what if b is root? what if $\beta$ is empty?)

Exercise 5: While right rotation lifts $\alpha$ and left rotation lifts $\gamma$, $\beta$ stays at the same level in both cases. Is it possible to (maybe by multiple rotations) lift $\beta$ one level (while dropping $\gamma$ and leaving $\alpha$ at the same level, or vice versa)?

References

  • D.D. Sleator, R.E. Tarjan, and W.P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 122-135. ACM, 1986. [bib] [pdf]

Splitting and merging nodes

Idea: Allow nodes containing multiple items and having multiple children (the tree will no longer be binary). If a node is too big, we can split it in two, if it is too small, we can borrow some elements from the neighbouring nodes or merge two small nodes together.

Used in: 2-3 tree, 2-3-4 tree, B-tree

Rebuilding the whole tree

Idea: This is a lazy approach: Just let the tree grow and from time to time, when things start to get bad (and the tree gets too imbalanced), rebuild the whole tree from scratch into a perfectly balanced tree.

Used in: Scapegoat tree