Chapter 6 · Transform-and-Conquer
Search Trees: BST, AVL, 2-3
A Binary Search Tree (BST) can degrade into a list. Two fixes change the representation: Adelson-Velsky–Landis (AVL) trees rotate to stay balanced, and 2-3 trees let a node hold two keys and grow from the top. Watch the height stay near log₂ n.
key travelling down (K)
being compared
new / overflowing / removed
unbalanced node / promoted key
found / fixed
node being checked
How to read this
- The orange ball
- It is the key K being inserted or searched for. It rides down the tree one comparison at a time: smaller goes left, larger goes right (in a 2-3 node it picks the left, middle or right pointer).
- Balance badges (AVL)
- The small badge on each AVL node is its balance factor: height(left subtree) − height(right subtree), where an empty tree has height −1. AVL trees allow only −1, 0, +1. A ±2 badge turns purple and triggers one of four rotations: R (single right), L (single left), LR (double left-right) or RL (double right-left).
- 2-3 nodes
- A box with one key is a 2-node (two children); a box with two keys is a 3-node (three children). A box that briefly shows three keys has overflowed and is about to split, sending its middle key up to the parent.
- Height readout
- Height counts edges on the longest root-to-leaf path (a single node has height 0). Compare it with ⌊log₂ n⌋, the best any binary tree with n keys can do, and with the guaranteed bounds for AVL trees (h < 1.4405 log₂(n + 2) − 1.3277) and 2-3 trees (log₃(n + 1) − 1 ≤ h ≤ log₂(n + 1) − 1), from Levitin §6.3.
Try this
- The book's AVL example. Pick AVL and build 5, 6, 8, 3, 2, 4, 7. You should see exactly four rotations, in this order: L(5), R(5), LR(6), RL(6). The final root is 5 and the height is 2.
- Worst case for a plain BST. Pick BST and press “Sorted 1..10”. Height 9 = n − 1: the tree is a linked list. Switch to AVL with the same keys: height 3. Switch to 2-3: height 2.
- The three delete cases. Build the BST 8, 3, 10, 1, 6, 14, 4, 7, 13. Delete 7 (a leaf), then 14 (one child), then 3 (two children: its in-order successor 4 takes its place).
- 2-3 growth. Pick 2-3 and build 9, 5, 8, 3, 2, 4, 7. Count the splits (4) and notice the tree only gets taller when the root splits, so all leaves always stay on one level.
- Search cost. After building any tree, search for a key that is not there. The number of comparisons is at most height + 1 for a BST or AVL tree.