HowToCodePage

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

Why an unbalanced BST degrades to a list, how rotations restore height balance, what red-black invariants buy over AVL, and why databases use wide B-tree nodes.

Balance is the difference between O(log n) and O(n)

A binary search tree keeps the invariant that everything left of a node is smaller and everything right is larger. Insert keys already sorted and the tree becomes a linked list with extra pointers.

insert 1,2,3,4,5 in order

1                3
 \              / \
  2            2   4
   \            \   \
    3            1   5
     \
      4            balanced
       \
        5        height log2(5) ~ 3
         height 5

A rotation is a local restructuring that preserves the in-order sequence and changes the height. Balanced trees differ mainly in how strictly they apply rotations and how much bookkeeping they keep.

The three families you will actually meet

TreeBalance ruleHeightInsert costWhere used
AVLHeights differ by at most 1about 1.44 log nMore rotations, tighter searchRead-heavy indexes
Red-blackColour rules bound the longest path to 2x the shortestabout 2 log nFewer rotations on writeJava TreeMap, C++ std::map, Linux scheduler
B-treeNode holds many keys; all leaves at the same depthlog with a big baseNode split rather than rotationDatabases, file systems
B+ treeB-tree with linked leavesSameSameRange scans in SQL indexes
# a BST delete has three cases — the third is where bugs live
def delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        if node.left is None:  return node.right
        if node.right is None: return node.left
        # two children: replace with in-order successor, then delete it
        succ = leftmost(node.right)
        node.key, node.value = succ.key, succ.value
        node.right = delete(node.right, succ.key)
    return node

Deletion with two children is the case that tests whether a tree implementation is correct. Using the in-order successor keeps the ordering valid, and the recursive delete on the successor's key handles its own case.

Why databases use wide nodes

A database index lives on disk. The cost of a lookup is not the number of comparisons but the number of pages read, so a node is sized to one page — often 4 KB or 8 KB, which means hundreds of keys per node and a very shallow tree.

  • A binary tree over a million keys is about 20 levels: 20 disk reads.
  • A B-tree with 200 keys per node needs about 3 levels for the same data: 3 reads.
  • Leaves are linked in a B+ tree, so a range scan walks sideways instead of re-descending.
  • Internal nodes are cached in memory, so usually only the leaf read costs a seek.
💡
In memory, a balanced binary tree is rarely the best choice. Cache locality favours a B-tree or a sorted array, which is why production containers often use B-trees even without a disk involved — the memory hierarchy pays the same kind of penalty as a disk seek.

FAQ

AVL or red-black?
AVL for read-dominated workloads because it is more tightly balanced and therefore shallower. Red-black for write-dominated workloads because an insert causes fewer rotations on average.
Why not just use a hash map?
A hash map cannot answer ordered queries. Range scans, predecessor and successor lookups, and ordered traversal all require a sorted structure.

Heaps and priority queues Benchmarking and testing your data structure

Last refreshed 2026-09-18.