Balanced Trees: AVL, Red-Black and B-Trees

See how AVL trees, red-black trees and B-trees keep search trees balanced with rotations and wide nodes, guaranteeing O(log n) for databases and libraries.

• Advanced
• 18 min read
• 4 objectives

Before this lessonLesson 10: Binary Search Trees

The previous lesson ended with a problem: a binary search tree fed sorted keys turns into a chain, and every operation drops to O(n). Self-balancing trees fix this by doing a little extra work on each insert and delete to keep the height close to log n, whatever order the keys arrive in.

You will rarely write one from scratch at work, but you use them all the time: Java's TreeMap, C++'s std::map and the Linux scheduler use red-black trees, and virtually every relational database index (PostgreSQL, MySQL InnoDB, SQLite) is a B-tree variant. Understanding how they work tells you why those tools are fast and when they are not.

The core tool: rotations

A rotation rearranges three nodes so one side of the tree becomes shorter and the other taller, while keeping the BST ordering intact. It changes only a few pointers, so it is O(1).

Right rotation at y:            Left rotation at x:

        y                x               x                   y
       / \              / \             / \                 / \
      x   C    ==>     A   y           A   y      ==>      x   C
     / \                  / \             / \             / \
    A   B                B   C           B   C           A   B

In-order stays A, x, B, y, C in both shapes.

Subtree B moves from x to y, but it still sits between x and y in sorted order, so the tree remains a valid BST.

AVL trees: strict balance

An AVL tree (1962, the first self-balancing BST) stores each node's height and enforces one rule: for every node, the heights of its left and right subtrees differ by at most 1. The difference is the balance factor. After an insert, walk back up the path; if a node's balance factor becomes 2 or -2, fix it with one or two rotations:

• Left-Left (new key went into the left child's left side): one right rotation.
• Right-Right: one left rotation.
• Left-Right: left-rotate the left child, then right-rotate the node.
• Right-Left: right-rotate the right child, then left-rotate the node.

class Node:
    def __init__(self, key):
        self.key, self.left, self.right, self.height = key, None, None, 1

def h(n):
    return n.height if n else 0

def update(n):
    n.height = 1 + max(h(n.left), h(n.right))

def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update(y); update(x)
    return x

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update(x); update(y)
    return y

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    update(node)
    balance = h(node.left) - h(node.right)
    if balance > 1:                       # left heavy
        if key > node.left.key:           # Left-Right case
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1:                      # right heavy
        if key < node.right.key:          # Right-Left case
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

root = None
for k in range(1, 8):          # sorted input, the worst case for a plain BST
    root = insert(root, k)

def show(n, depth=0):
    if n:
        show(n.right, depth + 1)
        print("    " * depth + str(n.key))
        show(n.left, depth + 1)

show(root)
print("height:", root.height)

        7
    6
        5
4
        3
    2
        1
height: 3

The tree is printed sideways (root on the left, right subtree above). Seven sorted inserts produced a perfect tree of height 3 instead of a chain of height 7. Let's measure it at scale.

import math

class Node:
    def __init__(self, key):
        self.key, self.left, self.right, self.height = key, None, None, 1
def h(n): return n.height if n else 0
def update(n): n.height = 1 + max(h(n.left), h(n.right))
def rotate_right(y):
    x = y.left; y.left = x.right; x.right = y; update(y); update(x); return x
def rotate_left(x):
    y = x.right; x.right = y.left; y.left = x; update(x); update(y); return y
def insert(node, key):
    if node is None: return Node(key)
    if key < node.key: node.left = insert(node.left, key)
    else: node.right = insert(node.right, key)
    update(node)
    b = h(node.left) - h(node.right)
    if b > 1:
        if key > node.left.key: node.left = rotate_left(node.left)
        return rotate_right(node)
    if b < -1:
        if key < node.right.key: node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

for n in [1_000, 100_000]:
    root = None
    for k in range(n):
        root = insert(root, k)
    print(n, "sorted keys -> height", root.height, "| log2(n) =", round(math.log2(n), 1))

1000 sorted keys -> height 10 | log2(n) = 10.0
100000 sorted keys -> height 17 | log2(n) = 16.6

AVL trees are guaranteed to stay under about 1.44 log2 n tall, so lookups are very fast. The price is more rotations on inserts and deletes.

Red-black trees: relaxed balance

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

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

Together these guarantee the longest path is at most twice the shortest, so height stays below 2 log2(n + 1). That is looser than AVL, which means slightly slower lookups but fewer rotations: an insert needs at most 2 rotations and a delete at most 3, with the rest of the fix-up done by cheap recolouring. That makes red-black trees a good default for general-purpose, write-heavy maps, which is why standard libraries favour them.

B-trees: balance for disks

Binary trees assume following a pointer is cheap. On disk or SSD, each node visit can mean reading a whole page (often 4 to 16 KB), and a binary tree with a billion keys is about 30 levels deep: 30 slow reads per lookup. A B-tree makes each node wide instead. A node holds many sorted keys (hundreds) and has one more child than keys. All leaves sit at the same depth, so the tree is perfectly balanced by construction.

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

Search 50: at the root, 30 < 50 < 60, go to the middle child, find 50.

When a node overflows on insert, it splits in two and pushes its middle key up to the parent. If the root splits, a new root is created, which is the only way the tree grows taller. With a branching factor of 500, three levels hold 500 cubed, about 125 million keys, and the top levels usually stay cached in memory.

import math

def levels(n_keys, fanout):
    return math.ceil(math.log(n_keys, fanout))

for fanout in [2, 100, 500]:
    print(f"fanout {fanout:>3}: {levels(1_000_000_000, fanout)} levels for 1 billion keys")

fanout   2: 30 levels for 1 billion keys
fanout 100: 5 levels for 1 billion keys
fanout 500: 4 levels for 1 billion keys

Databases mostly use the B+ tree variant: all values live in the leaves, internal nodes hold only keys for routing, and leaves are linked together, so a range scan like WHERE price BETWEEN 10 AND 20 finds the first leaf and then walks sideways.

Comparing the three

                  AVL                Red-black              B-tree / B+ tree
Max height        ~1.44 log2 n       ~2 log2 n              log_m n (m = fanout, hundreds)
Search            O(log n), fastest  O(log n)               O(log n), fewest disk reads
Insert/delete     O(log n), more     O(log n), at most      O(log n), splits and merges
                  rotations          2-3 rotations
Best for          read-heavy memory  general in-memory      databases, file systems
                  lookups            maps and sets
Used in           some in-memory     Java TreeMap, C++      PostgreSQL, MySQL InnoDB,
                  indexes            std::map, Linux CFS    SQLite, NTFS, ext4 dirs

Recap

• Self-balancing trees keep height O(log n) no matter the insert order.
• Rotations fix imbalance in O(1) while preserving BST order.
• AVL trees balance strictly (fast reads); red-black trees balance loosely (cheaper writes).
• B-trees use wide nodes so a lookup touches only a few disk pages; B+ trees add linked leaves for range scans.
• Use library implementations in real code.

# Write your solution here