Tag
tree-rotations
- Oct 23, 2026 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. data structures
- Nov 29, 2024 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. data structures
- Oct 7, 2024 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. data structures
- Sep 11, 2024 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. data structures
- May 14, 2024 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. data structures
- Dec 7, 2023 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. data structures
- Oct 19, 2023 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. data structures