Advanced · Module 20
Balanced trees
Keep trees shallow under any insertion order: AVL, red-black and B-trees.
A binary search tree is only as fast as it is shallow, and plain trees let ordinary input, like sorted ids, turn them into chains. This module covers the trees that guarantee their shape: AVL trees with strict height balance, red-black trees with a looser rule and cheaper updates, and B-trees with wide nodes sized for pages and caches. It ends with a practical guide to choosing between trees, heaps, sorted arrays and the ordered containers your language actually provides.
- 1Why binary search trees degradePro — members onlyA binary search tree is only as fast as it is shallow, and its shape depends entirely on insertion order. Sorted input turns it into a linked list. Balanced trees fix the shape as they go.13 min
- 2AVL rotationsPro — members onlyAn AVL tree keeps the heights of every node's two subtrees within one of each other. After an insert, at most one or two rotations, local pointer rearrangements that preserve key order, restore that rule and keep the height below 1.44 log₂ n.15 min
- 3Red-black treesPro — members onlyA red-black tree colors each node red or black and requires every path from a node down to its leaves to cross the same number of black nodes. That looser rule keeps the height under 2 log₂ n while needing at most two rotations per insert and three per delete.15 min
- 4B-trees and pagesPro — members onlyA B-tree stores hundreds of keys per node, sized to fit one disk page or a few cache lines, so a tree of billions of keys is only three or four levels tall. Nodes split as they fill, and the tree grows at the root, keeping every leaf at the same depth.15 min
- 5Choosing an ordered structurePro — members onlySorted arrays, heaps, balanced trees, skip lists and B-trees all keep data in order, with very different costs. The right choice follows from which operations you need, how often the data changes, and what your language provides.14 min