LLRB Trees, Splay Trees & B-Trees
Step through the code line-by-line to see how unique_ptr ownership
changes during rotations and insertions. Each step shows which pointer owns which node.
A splay tree moves accessed nodes to the root via rotations. This improves future access to the same or nearby nodes (locality of reference). Step through each splay operation to see how the tree restructures.
When the target is a direct child of the current subtree root, a single rotation brings it to the top.
Left child: Rotate right
Right child: Rotate left
This is the final step of a splay when the target is one level away from the subtree root.
Target X and its parent P are both on the same side (both left children or both right children).
Key: Rotating at the grandparent first (instead of the parent) is what distinguishes splaying from naive rotate-to-root, and gives the amortized O(lg N) guarantee.
Target X and its parent P are on opposite sides (e.g., P is a left child but X is P's right child).
Similar to an AVL double rotation. X moves up two levels: first past its parent, then past its grandparent.
Watch a complete splay bring a deep node all the way to the root by repeatedly applying zig, zig-zig, or zig-zag.
Build a demo tree first, then access a node to see the full splay in action.
A B-tree of order M is a self-balancing tree where each node can have multiple keys and children. This visualization shows insertion with node splitting when nodes exceed capacity.