Self-balancing trees: lift the taller side

The binary search trees lesson ended on its worst case: insert keys in sorted order and each one goes right of the last, so the tree becomes a chain and a search walks past every key. Real data often arrives sorted, so a plain search tree can't promise O(log n).

A self-balancing tree keeps that promise by repairing its shape as keys arrive. The AVL tree, published by Adelson-Velsky and Landis in 1962, watches how much taller one side of each node is than the other. When an insert makes one side two levels taller, a rotation lifts that side up: a few links change, the keys stay in order, and the seven sorted keys that made a chain of 7 levels come out 3 levels tall.

height

The number of levels in a subtree, as in the last lesson: a leaf has height 1 and an empty subtree 0. Each AVL node stores its own.

balance factor

A node's left height minus its right height: +1 means its left side is one level taller, −1 its right side, 0 level. (Some books subtract the other way round.)

AVL rule

On top of the search-tree rule, every node's balance factor is −1, 0 or +1. A node at +2 or −2 must be fixed.

rotation

Lifting one child of a node into the node's place and moving the node down to the other side. A few links change; the keys stay in order.

the four cases

Named by the path from the node at ±2 down its taller side: left-left and right-right are straight, left-right and right-left are bent.

These are the seven keys that made a chain in the plain tree, inserted in the same order. To the right of each node are its balance factor, above, and its height, below (h1, h2 …).

The repairs happen one insert at a time. In the smallest case, 30 has a left child, 20, and nothing on its right, so it already leans left by one.

Insert walks down as in a plain search tree. The new part is the walk back up the same path: each node recomputes its height as 1 + its taller child's height, then its balance factor. Nodes off the path gained nothing, so they can't have changed.

At 30 the path went left and left again, so 20 moved up and 30 moved down to its right. The keys still read 10, 20, 30 from left to right, and the subtree is 2 levels tall again, as before 10 arrived, so nothing above it changes.

That path was straight. If it bends, left and then right, one rotation is not enough.

So there are four cases. Left-left takes one right rotation and right-right one left rotation. Left-right takes a left rotation at the child, then a right rotation at the node, and right-left is its mirror. In the pseudo-code: if the node leans left (bf > 1) and its left child leans right (bf(left) < 0), straighten the child first.

Before each step, predict which way the walk goes, and at a node that reaches ±2, which rotation fixes it. This tree starts empty. Insert 10, then 30, then 20. Then undo the 20, insert 40 instead, and compare the two fixes.

A rotation is a few assignments. This program builds the chain from the first rotation, 30 above 20 above 10, and rotates it right. lifted is the child that moves up.

class BstNode:
    def __init__(self, key, left):
        self.key = key
        self.left = left
        self.right = None

def rotate_right(node):
    lifted = node.left
    node.left = lifted.right
    lifted.right = node
    return lifted

root = BstNode(30, BstNode(20, BstNode(10, None)))
print('root ' + str(root.key))
root = rotate_right(root)
print('root ' + str(root.key))
print(str(root.left.key) + ' < ' + str(root.key) + ' < ' + str(root.right.key))

Two links change inside the subtree, and the caller stores the returned node where 30 hung (here root): three links, however big the subtrees below, so a rotation is O(1). The last line prints 10 < 20 < 30: the order survives. Besides the two nodes that trade places, only the lifted child's inner subtree changes parent, and its keys all lie between those two. An AVL node also stores its height, so recompute the lowered node's, then the lifted node's. A left rotation is the mirror image.

Why does a bent case need two rotations? Think back to the insert of 25.

Delete works the same way: remove the key as in a plain search tree, then walk back up, updating heights and rotating wherever a node reaches ±2.

One rotation was enough here, but after a delete the rotated subtree can end up a level shorter than before, which can tip the node above it, and so on: at worst one rotation per level, still O(log n). The walk checks every node on the path, because the rule covers every node.

Within 1 is enough: the fewest keys an AVL tree of a given height can hold grow like the Fibonacci numbers, so its height stays below about $1.44 \log_2 n$. A million keys take at most 28 levels; no binary tree fits them in fewer than 20, and the sorted chain took a million. Red-black trees, behind Java's TreeMap and the usual C++ std::map, balance more loosely (height up to about $2 \log_2 n$) but need at most three rotations per insert or delete: cheaper updates, slightly slower lookups.

• An AVL tree is a binary search tree whose every node has a balance factor (left height minus right height) of −1, 0 or +1.
• Insert and delete work as in a plain search tree, then walk back up updating heights and rotating at any node at ±2. Straight cases need one rotation; bent cases rotate the child first.
• A rotation rewires three links and keeps the keys in order: O(1). An insert needs at most one single or double rotation; a delete may need one per level.
• The height stays below about 1.44 log₂ n, so search, insert and delete are O(log n) in the worst case, whatever the order of the keys.
• Next: B-trees, which pack many keys into each node (try the B-tree visualiser), and storage engines, where a variant, the B+ tree, holds database indexes. Practise with Check a Binary Tree Is Balanced and Depth of a Binary Tree, or open the AVL tree visualiser.