Balanced trees

Binary trees & BSTs showed that search, insert and delete each cost one step per level, and that inserting values in sorted order builds a chain as tall as the number of values. A balanced tree repairs itself after every change so that its height stays O(log n), whatever the order of the changes.

The usual measure is the balance factor of a node: the height of its left subtree minus the height of its right subtree, where an empty subtree has height 0. A tree is height-balanced when every node's balance factor is −1, 0 or 1.

A node's height needs both its children's heights first, so the check runs in postorder: each call returns its subtree's height, or −1 as soon as something below is unbalanced. The tree in the walkthrough is what a plain search tree looks like after inserting 5, 3, 8, 2, 4 and then 1.

Every node from 3 down is fine. Only the root is off: its left side is three levels deep and its right side one.

The repair is a tree rotation. A right rotation at node 30 with left child 20 makes 20 the top of that subtree and 30 its right child. Whatever hung on 20's right, values between 20 and 30, moves across to become 30's left subtree. A left rotation is the mirror image.

An AVL tree is a binary search tree that stays height-balanced. Each node remembers its height. After an ordinary insert, the recursion returns up the path it came down; at each node it updates the height and computes the balance factor. The first node found at +2 or −2 is repaired with a rotation, and that one repair always restores the balance of everything above it.

When the new value went down the same side twice (left of the left child, or right of the right child), one rotation fixes it. The walkthrough inserts values that only ever cause that straight-line case. Real AVL nodes store their height in a field; here the heights live in a map from value to height, because the pseudocode's tree nodes have only a value and two children.

If the new value went left, then right (or right, then left), a single rotation at the unbalanced node just moves the bend to the other side. The fix is two rotations: first rotate the child the other way, which turns the zigzag into a straight line, then rotate at the unbalanced node as before. This is the double rotation, and it completes the four cases of the AVL insert.

Deleting works the same way, except that more than one node on the way up may need a repair: O(log n) rotations at most, each O(1).

A red-black tree is the other common design. Every node is colored red or black, no red node has a red child, and every path from a node down to an empty spot passes the same number of black nodes. That bounds the height at 2 log₂(n + 1), looser than an AVL tree's roughly 1.44 log₂ n, but an insert or delete needs at most a few rotations, so updates are cheaper. Java's TreeMap and TreeSet are documented as red-black trees, and C++ standard libraries use them for std::map and std::set.

Python has no balanced tree in its standard library; the third-party sortedcontainers package is the usual stand-in. You will rarely write an AVL or red-black tree by hand. You will often need to recognize that a problem wants an ordered map: sorted keys that change as you go.