Splay Tree
Visualize a self-adjusting search tree that moves recently accessed elements to the root.
Free theory articleVisualize a self-adjusting search tree that moves recently accessed elements to the root.
Concept & interpretation
A Splay Tree is a self-adjusting binary search tree that stores no explicit height or color metadata. Instead, every insertion, lookup, or access performs a sequence of double rotations (splaying) that moves the accessed node x all the way to the root while roughly halving the depth of every node along the access path, achieving O(log n) amortized time per operation.
Interactive Experiment: What to Enter and Observe
Open the Splay Tree module to watch newly inserted keys splay to the root and observe the sequence of Zig, Zig-Zig, and Zig-Zag steps:
- Set Nodes to Insert to
10and Animation Speed to1200ms. - Note the first value in the Pending Insertions queue, then click Play.
- For each insertion, confirm two things on the canvas and in the Status card: (a) the newly inserted value always finishes at the amber-highlighted root node at the top of the canvas, and (b) the Status card lists the exact sequence of splay steps (e.g.,
Zig-Zag (Left-Right) -> Zig (Right)) used to bring it there. - Press Pause when a deep leaf is inserted to compare how a
Zig-Zigstep restructures the path into a more balanced subtree before the next key is inserted.