I want to explain splay trees the way I understood them when studying self-adjusting data structures. A splay tree is a type of binary search tree that automatically moves recently accessed elements closer to the root through a process called “splaying.” I find this data structure interesting because it adapts to usage patterns — frequently accessed elements become faster to reach over time, which is different from a standard balanced tree that treats every element equally regardless of access frequency.
History and Background
I learned that splay trees were invented by Daniel Sleator and Robert Tarjan in 1985, introduced in their paper “Self-Adjusting Binary Search Trees.” They designed splay trees as a simpler alternative to strictly balanced trees like AVL or red-black trees, proving that even though a single operation could take longer than in a balanced tree, the amortized cost over a sequence of operations remained efficient, which was a novel way of thinking about data structure performance at the time.
Problem Statement
The problem I need a splay tree to solve is efficient access to data where some elements are accessed far more often than others. A standard balanced binary search tree gives me guaranteed $O(\log n)$ time for every operation, but doesn’t take advantage of skewed access patterns. I want a structure that gets faster for frequently accessed items without me having to manually reorganize the data.
Core Concepts
- Splaying – the process of moving a node to the root of the tree using a sequence of rotations.
- Rotation – restructuring the tree locally to change which node is a parent versus a child, while preserving binary search tree order.
- Zig, Zig-Zig, Zig-Zag – the three rotation patterns used depending on the position of the accessed node relative to its parent and grandparent.
- Amortized analysis – analyzing average cost per operation over a sequence of operations, rather than worst-case cost of a single operation.
How It Works
- I search for a target key just like in a normal binary search tree, following left/right comparisons.
- Once I find (or nearly find) the node, I “splay” it — repeatedly rotate it upward until it becomes the root.
- During splaying, I use one of three rotation types depending on the node’s position: Zig (node’s parent is the root), Zig-Zig (node and parent are both left children or both right children), or Zig-Zag (node is a left child and parent is a right child, or vice versa).
- After splaying, the accessed node sits at the root, meaning future accesses to it will be immediate.
Working Principle
The internal logic relies on rotations that preserve the binary search tree property (left subtree values less than the node, right subtree values greater) while restructuring the path from root to the accessed node. By always moving accessed nodes to the root, frequently used data naturally clusters near the top of the tree, reducing the average search path length over time, even though the tree isn’t kept strictly balanced like an AVL tree.
Mathematical Foundation
The key result I rely on is the amortized time bound. Sleator and Tarjan proved that any sequence of $m$ operations on a splay tree with $n$ elements takes:
$$O(m \log n)$$
total time, meaning the amortized cost per operation is $O(\log n)$, matching balanced trees on average, even though a single splay operation can take $O(n)$ time in the worst case (for example, splaying a deep node in a skewed tree). This is proven using a potential function argument, where the potential of the tree is defined based on the sum of logarithms of subtree sizes:
$$\Phi(T) = \sum_{x \in T} \log(\text{size}(x))$$
and the amortized cost of an operation is bounded using changes in this potential.
Diagrams
flowchart TD
A[Search for Key X] --> B{Found X or reached leaf}
B --> C[Splay X to Root using Zig/Zig-Zig/Zig-Zag rotations]
C --> D[X is now Root]Pseudocode
function SPLAY(root, key):
if root == NULL or root.key == key:
return root
if key < root.key:
if root.left == NULL: return root
// Zig-Zig (left-left)
if key < root.left.key:
root.left.left = SPLAY(root.left.left, key)
root = ROTATE_RIGHT(root)
// Zig-Zag (left-right)
else if key > root.left.key:
root.left.right = SPLAY(root.left.right, key)
if root.left.right != NULL:
root.left = ROTATE_LEFT(root.left)
if root.left == NULL: return root
return ROTATE_RIGHT(root)
else:
if root.right == NULL: return root
// Zig-Zag (right-left)
if key < root.right.key:
root.right.left = SPLAY(root.right.left, key)
if root.right.left != NULL:
root.right = ROTATE_RIGHT(root.right)
// Zig-Zig (right-right)
else if key > root.right.key:
root.right.right = SPLAY(root.right.right, key)
root = ROTATE_LEFT(root)
if root.right == NULL: return root
return ROTATE_LEFT(root)
Step-by-Step Example
Suppose I have a tree with root 10, and I access key 2, where the path from root to 2 is 10 → 5 → 2 (2 is the left child of 5, and 5 is the left child of 10).
- Since 2 is a left-left (Zig-Zig) pattern relative to grandparent 10, I perform a Zig-Zig rotation.
- First rotate right at 10, then rotate right again to bring 2 all the way up.
- After splaying, 2 becomes the new root, with 5 and 10 rearranged beneath it, preserving BST order.
- If I access 2 again immediately afterward, it takes just $O(1)$ time since it’s already the root.
Time Complexity
- Best case: $O(1)$ if the accessed element is already the root.
- Average/amortized case: $O(\log n)$ over a sequence of operations.
- Worst case (single operation): $O(n)$, which can occur if the tree is heavily skewed before splaying.
Space Complexity
Space complexity is $O(n)$ to store $n$ nodes, and the recursive splay operation uses $O(\log n)$ to $O(n)$ additional space on the call stack, depending on tree shape, though iterative implementations can reduce this to $O(1)$ extra space.
Correctness Analysis
I trust splay trees are correct because every rotation used during splaying preserves the binary search tree invariant — rotations only change parent-child relationships locally without violating the left-less-than-node-less-than-right ordering. Since the tree remains a valid BST after every splay, search, insert, and delete operations continue to behave correctly.
Advantages
- Frequently accessed elements become very fast to access over time.
- Simpler to implement than strictly balanced trees like red-black or AVL trees, since no extra balance metadata (colors, heights) is needed.
- Performs well in practice for real-world access patterns that aren’t uniformly random.
- Good amortized performance guarantees despite simple implementation.
Disadvantages
- Individual operations can be slow ($O(n)$ worst case), which is unacceptable for real-time systems needing consistent per-operation guarantees.
- Not thread-safe by default since every access modifies the tree structure, even reads.
- Performance depends heavily on access patterns; uniformly random access doesn’t benefit much from splaying.
Applications
I’ve seen splay trees used in caching systems, garbage collection algorithms, network routers for packet processing, data compression algorithms, and in implementing efficient “least recently used”-style structures where access patterns are skewed.
Implementation in C
Here’s a simplified splay tree implementation in C supporting search-and-splay.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
struct Node *left, *right;
} Node;
Node* new_node(int key) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->left = node->right = NULL;
return node;
}
Node* rotate_right(Node* y) {
Node* x = y->left;
y->left = x->right;
x->right = y;
return x;
}
Node* rotate_left(Node* x) {
Node* y = x->right;
x->right = y->left;
y->left = x;
return y;
}
// Splays the tree so that the node with 'key' becomes root (if it exists)
Node* splay(Node* root, int key) {
if (root == NULL || root->key == key) return root;
if (key < root->key) {
if (root->left == NULL) return root;
if (key < root->left->key) { // Zig-Zig
root->left->left = splay(root->left->left, key);
root = rotate_right(root);
} else if (key > root->left->key) { // Zig-Zag
root->left->right = splay(root->left->right, key);
if (root->left->right != NULL)
root->left = rotate_left(root->left);
}
return (root->left == NULL) ? root : rotate_right(root);
} else {
if (root->right == NULL) return root;
if (key < root->right->key) { // Zig-Zag
root->right->left = splay(root->right->left, key);
if (root->right->left != NULL)
root->right = rotate_right(root->right);
} else if (key > root->right->key) { // Zig-Zig
root->right->right = splay(root->right->right, key);
root = rotate_left(root);
}
return (root->right == NULL) ? root : rotate_left(root);
}
}
Node* insert(Node* root, int key) {
if (root == NULL) return new_node(key);
root = splay(root, key);
if (root->key == key) return root;
Node* new_root = new_node(key);
if (key < root->key) {
new_root->right = root;
new_root->left = root->left;
root->left = NULL;
} else {
new_root->left = root;
new_root->right = root->right;
root->right = NULL;
}
return new_root;
}
void inorder(Node* root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
int main() {
Node* root = NULL;
int values[] = {10, 5, 20, 2, 8};
for (int i = 0; i < 5; i++) {
root = insert(root, values[i]);
}
printf("Inorder traversal: ");
inorder(root);
printf("\n");
root = splay(root, 2);
printf("Root after splaying key 2: %d\n", root->key);
return 0;
}
Sample Input and Output
Input: Insert keys 10, 5, 20, 2, 8, then splay key 2 to the root.
Output:
Inorder traversal: 2 5 8 10 20
Root after splaying key 2: 2
Optimization Techniques
I improve splay tree performance by using iterative (bottom-up) splaying instead of recursive top-down splaying to reduce stack overhead, batching multiple operations before re-splaying when possible, and combining splay trees with other structures for specific workloads (like splay trees for caching combined with hash maps for direct lookups).
Common Mistakes
I’ve noticed people confuse the three rotation cases (Zig, Zig-Zig, Zig-Zag), which leads to incorrect tree restructuring, forget to splay after insertions and deletions (not just searches), and assume splay trees give worst-case $O(\log n)$ per operation, when the guarantee is only amortized over a sequence of operations.
Further Reading
- Sleator, D. & Tarjan, R., “Self-Adjusting Binary Search Trees” – https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
- CLRS “Introduction to Algorithms” (splay tree exercises and amortized analysis chapters) – https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Stanford CS166 Lecture Notes on Splay Trees – https://web.stanford.edu/class/cs166/
- GeeksforGeeks Splay Tree Explanation – https://www.geeksforgeeks.org/splay-tree-set-1-insert/
