Balanced trees: AVL, red-black and B-trees

The last lesson ended with a problem: a BST is only fast while it is short, and real data (sorted IDs, timestamps) easily makes it tall. A self-balancing tree fixes its shape automatically after every insert and delete, so its height always stays O(log n), whatever order the keys arrive in.

Rotations: reshaping without breaking the order

The basic tool is a rotation. A right rotation around node Y lifts its left child X up: X becomes the parent, Y becomes X’s right child, and X’s old right subtree moves across to become Y’s left subtree. The in-order sequence of keys does not change, so the BST rule still holds, but one side gets one level shorter. A left rotation is the mirror image. A rotation only changes a few pointers: O(1).

1      Y                    X2     / \     rotate       / \3    X   C    right       A   Y4   / \       ───→           / \5  A   B                     B   C6 7in-order before: A X B Y C     in-order after: A X B Y C

AVL trees

The AVL tree (1962, named after Adelson-Velsky and Landis) was the first self-balancing BST. Every node stores its height. Its balance factor is height(left) − height(right). The rule: every balance factor must be −1, 0 or +1. After an insert, walk back up the path; the first node whose factor became ±2 is fixed with one of four cases:

1var tree = new AvlTree();2for (int i = 1; i <= 1000; i++) tree.Insert(i);               // sorted: worst case for a BST3Console.WriteLine($"1,000 sorted inserts: height {tree.Height}");4for (int i = 1001; i <= 1_000_000; i++) tree.Insert(i);5Console.WriteLine($"1,000,000 sorted inserts: height {tree.Height}");6 7class AvlTree8{9    private class Node10    {11        public int Key, Height = 1;                 // height counted in nodes here12        public Node? Left, Right;13        public Node(int key) => Key = key;14    }15    private Node? _root;16 17    public int Height => H(_root) - 1;              // in edges, like the rest of the course18 19    private static int H(Node? n) => n?.Height ?? 0;20    private static void Update(Node n) => n.Height = 1 + Math.Max(H(n.Left), H(n.Right));21    private static int Balance(Node n) => H(n.Left) - H(n.Right);22 23    private static Node RotateRight(Node y)24    {25        var x = y.Left!;26        y.Left = x.Right;27        x.Right = y;28        Update(y);29        Update(x);30        return x;                                   // x is the new subtree root31    }32 33    private static Node RotateLeft(Node x)34    {35        var y = x.Right!;36        x.Right = y.Left;37        y.Left = x;38        Update(x);39        Update(y);40        return y;41    }42 43    public void Insert(int key) => _root = Insert(_root, key);44 45    private static Node Insert(Node? n, int key)46    {47        if (n is null) return new Node(key);48        if (key < n.Key) n.Left = Insert(n.Left, key);49        else if (key > n.Key) n.Right = Insert(n.Right, key);50        else return n;51 52        Update(n);53        int b = Balance(n);54        if (b > 1 && key < n.Left!.Key) return RotateRight(n);                  // left-left55        if (b < -1 && key > n.Right!.Key) return RotateLeft(n);                 // right-right56        if (b > 1) { n.Left = RotateLeft(n.Left!); return RotateRight(n); }     // left-right57        if (b < -1) { n.Right = RotateRight(n.Right!); return RotateLeft(n); }  // right-left58        return n;59    }60}

1,000 sorted inserts: height 9
1,000,000 sorted inserts: height 19

A plain BST would have heights 999 and 999,999 for the same input (and would overflow the stack long before that). The AVL tree stays at about log₂ n.

Red-black trees

A red-black tree colours every node red or black and keeps these rules:

• The root is black, and the empty (null) leaves count as black.
• A red node never has a red child.
• Every path from a node down to an empty leaf passes through the same number of black nodes.

Together these guarantee that the longest path is at most twice the shortest, so the height is at most about 2 log₂ n. That is a looser balance than AVL, so lookups can be slightly slower, but inserts and deletes need fewer rotations (at most 2 for an insert, 3 for a delete). That trade-off is why most libraries choose red-black trees: .NET’s SortedSet and SortedDictionary, Java’s TreeMap, and C++’s std::map.

B-trees: balanced trees for disks

Reading from disk or SSD is slow compared with memory, and data comes in pages (often 4 or 8 KB). A B-tree makes each node one page holding hundreds of keys and hundreds of children. With 500 children per node, three levels hold 500³ = 125 million keys, so any key is found in 3 or 4 page reads. All leaves are at the same depth, and nodes split or merge to stay balanced.

Almost every database index is a B-tree (more exactly a B+ tree, where all values live in the leaves and leaves are linked for fast range scans): SQL Server, PostgreSQL, SQLite, as well as file systems such as NTFS. When you create an index on a column, you are building one.

1var perfect = new Node(2, new Node(1), new Node(3));2var chain = new Node(1, null, new Node(2, null, new Node(3)));3 4Console.WriteLine(IsBalanced(perfect));5Console.WriteLine(IsBalanced(chain));6 7static bool IsBalanced(Node? root) => CheckedHeight(root) != -1;8 9static int CheckedHeight(Node? n)              // height in nodes, or -1 if unbalanced10{11    if (n is null) return 0;12    int left = CheckedHeight(n.Left);13    if (left == -1) return -1;14    int right = CheckedHeight(n.Right);15    if (right == -1) return -1;16    if (Math.Abs(left - right) > 1) return -1;17    return 1 + Math.Max(left, right);18}19 20record Node(int Key, Node? Left = null, Node? Right = null);

True
False