Balanced Trees

Overview

A binary search tree is O(log n) only while it stays short, and nothing in the plain insertion algorithm keeps it short. A self-balancing tree restores a height bound after every modification, converting the average case into a guarantee.

The mechanism is always the same: detect that the invariant broke, then apply local rotations — constant-time pointer rearrangements that change the shape without changing the in-order sequence.

Core Concepts

Structure	Balance invariant	Height bound	Typical use
AVL tree	Subtree heights differ by ≤ 1 at every node	≤ 1.44 log₂ n	Read-heavy workloads
Red-black tree	No red node has a red child; equal black-depth on all paths	≤ 2 log₂ n	Language library maps/sets
B-tree / B+ tree	All leaves at the same depth; nodes hold many keys	log_B n	Databases, filesystems
Trie	Not a search tree — position encodes the key	Length of the key	Prefix queries, autocomplete

Architecture / Mechanism

Rotations

A rotation swaps a parent and child while re-parenting one subtree, preserving the BST ordering:

      y                               x
     / \        right rotation       / \
    x   C       ───────────────>    A   y
   / \          <───────────────       / \
  A   B          left rotation        B   C

In-order before:  A x B y C
In-order after:   A x B y C      (identical — only the shape changed)

An AVL tree rebalancing as values are inserted. Each insertion may trigger one or two rotations, and the tree never gets taller than it must. Wikimedia Commons, CC BY-SA 4.0

AVL vs. red-black: the same idea, differently tuned

AVL keeps a strict bound (heights differ by at most 1) and so stays shorter, giving faster lookups. Red-black permits a looser bound and so rebalances less, giving faster insertion and deletion.

A red-black tree. The colours are one bit per node, and the two rules they encode are enough to guarantee the longest path is at most twice the shortest. Wikimedia Commons, CC BY-SA 3.0

	AVL	Red-black
Height	≤ 1.44 log₂ n — shorter	≤ 2 log₂ n
Lookup	Faster	Slightly slower
Insert / delete	More rotations	Fewer rotations
Rotations per delete	O(log n)	≤ 3
Used by	Some in-memory indexes	C++ map/set, Java TreeMap, Linux CFS scheduler, epoll

Red-black won the standard-library slot almost everywhere, because mixed read/write workloads are the common case and its worst-case deletion cost is a small constant.

B-trees: balanced for disks, not for RAM

Binary trees ask one question per node. When a node lives on storage and reading it costs an entire 4–16 KB page, that is a catastrophic ratio — you fetch 16 KB to learn one bit of information.

A B-tree sizes each node to one page and stores hundreds of keys in it, so a single I/O narrows the search hundreds of ways instead of two:

High fan-out is the point. With ~400 keys per node, three levels index 64 million entries — three disk reads for any lookup. Wikimedia Commons, CC BY-SA 3.0

B+ trees, the variant databases actually use, additionally keep all values in the leaves and link the leaves together, making a range scan a sequential walk rather than a repeated root-down descent.

Tries: keyed by position, not by comparison

A trie stores keys along the path rather than in the nodes, so no key comparison happens at all — lookup cost depends on key length, not on how many keys are stored:

Edges carry the characters; a node's path from the root *is* its key. Every word sharing a prefix shares the nodes for it. Wikimedia Commons, Public domain

This makes prefix operations — autocomplete, longest-prefix IP routing, dictionary matching — natural, which no comparison tree or hash table offers. The cost is memory: a naive trie allocates a child array per node, which is why practical implementations use compressed forms (radix trees, and the Patricia tries inside kernel routing tables).

Practical Usage

Language	Ordered map	Underlying structure
C++	std::map, std::set	Red-black tree
Java	TreeMap, TreeSet	Red-black tree
Python	(none built in)	Use sortedcontainers, or keep a sorted list + bisect
Rust	BTreeMap, BTreeSet	B-tree — chosen for cache behaviour, in memory
Go	(none built in)	Sort a slice, or use a third-party tree

Rust's choice is the interesting one

BTreeMap uses a B-tree in memory, not on disk, for exactly the reason B-trees were invented — just one level down the hierarchy. Here the "page" is a cache line, and packing many keys into one node means one cache miss narrows the search many ways instead of two. The same argument, applied to a different boundary.

Edge Cases & Pitfalls

• Do not implement one unless you must. Red-black deletion has many cases and is genuinely easy to get subtly wrong. Every mainstream standard library ships a correct one.
• A balanced tree is not a hash table. If you never need ordering, ranges or a worst-case bound, a hash table is faster and simpler.
• Tries can use far more memory than expected. One child pointer per alphabet symbol per node adds up quickly; measure before choosing one over a hash table for plain exact-match lookup.
• "Balanced" bounds height, not shape. Two trees holding the same keys can differ completely in structure depending on insertion order; only the height bound is guaranteed.

References

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 13 (red-black trees) and Ch. 18 (B-trees).
• Adelson-Velsky & Landis (1962) — the original AVL paper, and the first self-balancing BST.
• Rust BTreeMap documentation — the standard library's rationale for B-trees in memory.

Books & Videos

• VisuAlgo — AVL and Red-Black Trees — watch rotations happen step by step.

Related Pages

• Trees & Binary Search Trees — the unbalanced base case and why it degenerates.
• Hash Tables — the unordered alternative.
• Indexing & Storage Engines — B+ trees under real query loads.