Splay Tree Visualization
A Splay Tree is a self-adjusting binary search tree that reshapes itself based on how it’s used. Instead of trying to stay balanced all the time, it aggressively moves recently accessed nodes closer to the root. Over time, the tree adapts to access patterns rather than an abstract notion of balance. Splay trees are useful for ordered dictionaries or lookup tables with uneven access patterns, such as repeatedly looking up a small working set of identifiers.
How It Works
When you search, insert, or delete a node, the tree performs a series of rotations called "splaying" to bring that node to the root. There are three types of rotations depending on the node’s position: Zig (single rotation), Zig-Zig (double rotation in same direction), and Zig-Zag (double rotation in opposite directions).
After splaying, frequently accessed nodes stay near the root, making repeated operations faster. Each operation take O(log n) amortized time for n stored keys, with O(n) worst-case time for any single operation.
Key Operations
- Search: follow BST comparisons, then splay the matching node. If the key is absent, splay the last node visited.
- Insertion: place a new key as a leaf using the BST rule, then splay that new node to the root.
- Deletion: splay the key to the root and remove it. To join the remaining subtrees, splay the largest key in the left subtree and attach the right subtree as its right child. If the left subtree is empty, use the right subtree as the new tree.
AI Summary
(5 credits)
Common Interview Questions
How does "splaying" provide amortized O(log n) performance?
Splaying moves an accessed node to the root of the tree through a series of rotations, keeping frequently accessed elements near the root. While a single operation can take O(n), amortized cost over a sequence of M operations is guaranteed to be O(M log n).
What is a major advantage of Splay Trees regarding auxiliary memory metadata?
Splay Trees do not store any extra balance information (like height in AVL or color bits in Red-Black). This saves node memory footprint while maintaining self-balancing properties.
💬 Discussion
to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0