Splay Tree
Visualize a self-adjusting search tree that moves recently accessed elements to the root.
Splay Tree
Concept Overview
A Splay Tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of non-random operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown.
Mathematical Definition
The amortized performance of a splay tree is analyzed using the potential method. We define the size S(x) of a node x as the number of nodes in the subtree rooted at x, and its rank r(x) as the base-2 logarithm of its size:
r(x) = log2(S(x))
The potential function Φ of the tree is the sum of the ranks of all its nodes:
Φ = Σx ∈ Tree r(x)
Amortized Cost ≤ 3(r(root) - r(x)) + 1 = O(log n)
Key Concepts
- Splaying: The fundamental operation in a splay tree. When a node x is accessed, a splay operation is performed on x to move it to the root. This involves a sequence of splay steps.
- Zig Step: Executed when the node x to be splayed is a child of the root. It requires a single tree rotation.
- Zig-Zig Step: Executed when both x and its parent p are either left children or right children. It involves two rotations of the same kind.
- Zig-Zag Step: Executed when x and p are different kinds of children (one left, one right). It involves a double rotation.
Historical Context
The Splay Tree was invented by Daniel Sleator and Robert Tarjan in 1985. Their goal was to design a self-adjusting binary search tree that would automatically restructure itself to optimize for the access frequencies of its elements, achieving an optimal amortized time complexity without storing any balance information in the nodes.
Real-world Applications
- Caches: Highly effective for implementing caches, as recently accessed elements are kept near the root of the tree, providing very fast subsequent access.
- Memory Allocators: Used in implementations of malloc and memory management to keep track of available memory blocks, allowing quick access to frequently requested sizes.
- Garbage Collection: Employed in some garbage collection algorithms to maintain lists of free or used objects.
Related Concepts
- AVL Tree Rotations — another type of self-balancing binary search tree.
- Red-Black Tree — widely used balanced tree with a weaker balancing constraint.
- Lru Cache — caching strategy that can be implemented or conceptualized similarly to a splay tree's behavior.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Splay Tree module.
Try Splay Tree on Riano →