Data Structures · Cluster
Balanced Trees
Rotations, height invariants, and ordered maps.
- 01 Height Bounds and the Cost of a Degenerate Search Tree Why the worst-case depth of a binary search tree, not its average depth, sets lookup cost, and what a balance invariant has to constrain to fix it.
- 02 Rotations and the In-Order Sequence They Preserve How a single rotation rewires three pointers while keeping key order, why some violations need two rotations, and what a rotation cannot repair.
- 03 Balance Factors, and Why AVL Deletion Cascades How two bits per node encode the AVL invariant, why an insertion repair stops at the first rotation while a deletion repair can climb to the root, and what the child balance factor decides.
- 04 Red-Black Colouring as a Height Proxy How one bit per node encodes a 2-3-4 tree, why the colour rules make insertion repair terminate early, and where the two-to-one height constant comes from.
- 05 B-Tree Node Occupancy, Splits, and the Minimum Degree Why a B-tree fixes node size rather than height, how a split propagates to the root, and what the minimum degree buys in depth versus split frequency.
- 06 Weight-Balanced Trees and the Ratio That Bounds Depth Why subtree size is a usable balance weight, how the size ratio is chosen, and why size balance makes join and split the natural primitives.
- 07 Treaps: Priorities, Expected Depth, and Rotation-Only Updates How assigning a random priority per key turns a binary search tree into a heap-ordered structure with a probabilistic height bound, and what deletion by rotation costs.
- 08 Splaying: Amortized Restructuring Without Stored Balance How a splay step moves an accessed node to the root, why zig-zig pairing matters, and how a potential function yields O(log n) amortized access with zero metadata.
- 09 Order-Statistic Augmentation and Rank Queries How a subtree count maintained through every rotation answers rank and select in logarithmic time, and why the aggregate must be recomputable from children alone.
- 10 Path Copying and the Cost of Persistence in Balanced Trees Why an update to an immutable balanced tree rewrites one path, how the sharing structure changes the balance invariants, and where the allocation cost actually goes.