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:
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.
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?)
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.
- 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
- 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)
- 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)
- 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)?
- 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.
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