Balanced Trees & B-Trees

A binary search tree promises O(log n) search — but that promise holds only while the tree stays balanced. Feed it the wrong order of data and the promise quietly evaporates.

The collapse

Insert 1, 2, 3, 4, 5 in that order. Each value is larger than everything already there, so every insert turns right, and the tree grows into a single drooping line:

1
 \
  2
   \
    3
     \
      4
       \
        5

That is a linked list wearing a tree costume. Searching for 5 visits every node — height is n, search is O(n). The ordering rule is perfectly intact; it is the performance that is gone. And this is no contrived case: sorted data, reverse-sorted data, and many real access patterns produce exactly this shape. The cure is to keep the tree height-balanced, so that for n nodes the height stays near log₂ n — about 17 levels for a million nodes, not a million.

What a rotation does

A self-balancing tree adds one extra rule on top of the BST rule, and whenever an insert or delete breaks it, the tree repairs itself with a rotation — a tiny, local relinking that changes height without disturbing the order. Picture a left-heavy subtree, and a right rotation that lifts its left child up:

Read the order off both pictures: A, x, B, y, C, before and after. The values keep their relation, so search still works — but the subtree got one level shorter. That is the whole mechanical trick: no recopying, no rebuilding, just relinking three pointers. Two families of tree use it:

• An AVL tree keeps the two sides of every node within one level of each other, rotating eagerly to stay strictly even — best when reads dominate.
• A red-black tree uses a looser colouring rule, so it rotates less per insert. It backs most standard-library ordered maps — Java’s TreeMap, C++‘s std::map.

You rarely build these yourself; you reach for the library. But seeing the rotation makes clear why the library can promise O(log n) no matter what order the data arrives.

Watching the collapse in code

Let us measure the damage directly — insert 1 through 15 in sorted order into a plain BST and check its height against what a balanced tree would give:

import math

class Node:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

root = None
for i in range(1, 16):                 # 1..15, already sorted — the worst input
    root = insert(root, i)

print("nodes inserted          :", 15)
print("actual height           :", height(root))
print("a balanced tree would be:", math.ceil(math.log2(16)))

nodes inserted          : 15
actual height           : 15
a balanced tree would be: 4

Height 15 where 4 was possible — a search for the last value now visits all fifteen nodes. That gap is exactly what AVL and red-black trees rotate away.

B-trees: trading depth for width

Self-balancing BSTs fix the problem in memory. Databases face a different enemy: the data lives on disk, and a single disk read costs thousands of times more than a memory access — so the goal becomes minimising reads, not comparisons.

A binary tree of a million nodes is about 20 levels deep, and if each node sits on its own disk page, that is up to 20 reads to find one row. A B-tree flattens this by widening each node: instead of two children, a node holds hundreds of keys and hundreds of child pointers, sized to fill exactly one disk page.

         [30 | 70]
        /     |     \
 [10|20]   [40|50|60]   [80|90]

That toy has fan-out 3; real indexes use fan-out in the hundreds. A B-tree only 3 or 4 levels tall can index tens of millions of rows, and each level is one disk read. Databases almost always use the B+-tree variant, where the actual records live only in the leaves, internal nodes are pure routing, and the leaves are chained in sorted order — so a range query like WHERE price BETWEEN 10 AND 50 finds the start and then just walks the leaf chain.

Practice