Balanced Search Trees
Teach the motivation, invariants, rotations, insertion/deletion, proofs at an intuitive level, and complexity:
AVL trees: balance factor, single/double rotations.
Red-black trees: coloring rules and fix-up cases.
B-trees and B+ trees: multiway indexing and disk/page locality.
2–3 trees and 2–3–4 trees.
Splay trees and amortized behavior.
Treaps: BST order plus heap priority.
Segment tree and interval tree are separate range-query structures, not ordinary search-tree replacements.
Students should be able to trace rotations and verify invariants after each update.
13.1 Rotations
A rotation changes the tree's shape while preserving the inorder (sorted) order:
Text equivalent: before, y has left child x (with subtrees A and B) and right subtree C. After a right rotation, x is on top with left subtree A and right child y, and y adopts B as its left subtree. The inorder order A, x, B, y, C is unchanged.
flowchart TD
subgraph Before[Before right rotation at y]
Y1[y] --> X1[x]
Y1 --> C1[C]
X1 --> A1[A]
X1 --> B1[B]
end
subgraph After[After]
X2[x] --> A2[A]
X2 --> Y2[y]
Y2 --> B2[B]
Y2 --> C2[C]
end13.2 AVL trees
The AVL invariant: at every node, the heights of the two subtrees differ by at most 1 (balance factor in {−1, 0, 1}). After an insertion, walk back up; at the first unbalanced node there are four cases — left-left and right-right need one rotation; left-right and right-left need two.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
An AVL tree with n nodes has height below 1.44 log₂(n + 2), so 100 000 sorted insertions — which would build a 99 999-deep chain in a plain BST — give height 16. The check function verifies the order, stored heights and balance factors after every phase, and the deletions are compared against std::set.
#include <bits/stdc++.h>
using namespace std;
struct Node { int key, h = 0; Node* l = nullptr; Node* r = nullptr; explicit Node(int k) : key(k) {} };
int H(Node* n) { return n ? n->h : -1; }
void pull(Node* n) { n->h = 1 + max(H(n->l), H(n->r)); }
int balance(Node* n) { return H(n->l) - H(n->r); }
int rotations = 0;
Node* rotateRight(Node* y) { Node* x = y->l; y->l = x->r; x->r = y; pull(y); pull(x); ++rotations; return x; }
Node* rotateLeft(Node* x) { Node* y = x->r; x->r = y->l; y->l = x; pull(x); pull(y); ++rotations; return y; }
Node* rebalance(Node* n) {
pull(n);
if (balance(n) > 1) { // left heavy
if (balance(n->l) < 0) n->l = rotateLeft(n->l); // left-right case
return rotateRight(n);
}
if (balance(n) < -1) { // right heavy
if (balance(n->r) > 0) n->r = rotateRight(n->r); // right-left case
return rotateLeft(n);
}
return n;
}
Node* insert(Node* n, int k) {
if (!n) return new Node(k);
if (k < n->key) n->l = insert(n->l, k);
else if (k > n->key) n->r = insert(n->r, k);
else return n;
return rebalance(n);
}
Node* eraseMi
…insert 10: (10)
insert 20: (10(20))
insert 30: ((10)20(30))
insert 25: ((10)20((25)30))
insert 28: ((10)20((25)28(30)))
100000 sorted inserts: height 16, rotations 99983, valid AVL: true
after 60000 random deletions: 54860 keys, matches std::set: true, height 16, valid AVL: true13.3 Red-black trees
Each node is red or black; the root and the nil leaves are black; a red node has black children; every root-to-leaf path has the same number of black nodes. These rules force the longest path to be at most twice the shortest, giving height ≤ 2 log₂(n + 1). Insertion fixes violations with recoloring plus at most two rotations; deletion with at most three. std::map and std::set are red-black trees in the common standard libraries — slightly less strictly balanced than AVL, with fewer rotations on update.
13.4 B-trees and B+ trees
A B-tree node holds many sorted keys (often hundreds) and has one more child than keys, sized to fill a disk page. Height is O(log_B n) with large B, so a billion keys need only three or four page reads. B+ trees keep all records in the leaves and link the leaves for range scans — the index structure of most relational databases and file systems. A 2–3 tree is a B-tree of order 3; a 2–3–4 tree corresponds exactly to a red-black tree.
13.5 Splay trees and treaps
Splay tree: every access rotates the accessed node to the root. No balance information is stored; any sequence of m operations costs O(m log n) amortized, and recently used keys become fast to reach.
Treap: each node gets a random priority; the tree is a BST by key and a heap by priority. Its shape is that of a BST built from keys in priority order — a random BST — so the expected height is O(log n).
Practice
Easy: insert 3, 2, 1 into an AVL tree by hand; name the case and the rotation.
Medium: add subtree sizes to the AVL tree and implement select(i).
Hard: implement a treap with split and merge, and verify it against std::set with a stress test.
Quiz
? Inserting 10, 20, 30 into an empty AVL tree triggers which fix?
+ A single left rotation at 10 (right-right case) :: The run shows the tree becoming (10)20(30).
- A double rotation :: That is the right-left or left-right case.
- None :: 10 would have balance −2.
- Recoloring :: That is red-black trees.
? Why do databases use B+ trees rather than binary search trees for indexes?
+ Wide nodes match disk pages, so the height and the number of page reads stay tiny, and linked leaves make range scans fast. :: Locality matters more than comparisons.
- They use less CPU per comparison. :: Not the main reason.
- Binary trees cannot be stored on disk. :: They can, inefficiently.
- B+ trees never need rebalancing. :: They split and merge nodes.
? Which statements about balanced trees are correct? (select all that apply)
+ Rotations preserve the inorder order of keys. :: That is why they are safe.
+ AVL height is below about 1.44 log₂ n. :: The run's 100 000 keys gave height 16.
+ std::map is typically a red-black tree. :: libstdc++ and libc++ both use one.
- Segment trees are a drop-in replacement for search trees. :: They answer range queries over positions.