Splay Tree
A self-adjusting BST that pays for flexibility with amortized analysis instead of explicit balance invariants.
Splay Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
A splay tree is a binary search tree that refuses to keep a fixed balance condition. Instead, whenever a node is accessed, the tree rotates that node to the root. The shape keeps changing, but the total cost over a sequence of operations stays logarithmic on average.
That tradeoff makes splay trees unusually important in competitive programming. They can act like an ordered set, an implicit sequence, a cut-and-paste editor, or the preferred-path engine inside a link-cut tree. The code is more fragile than a treap, but the payoff is that one splay core unlocks several advanced structures.
When to Use It
I think about a splay tree when:
I want split and merge plus ordered-set operations,
I need sequence operations such as reverse, cut, paste, or range aggregate,
I want a fully pointer-based BST without randomization,
the same balancing machinery will later be reused for link-cut trees.
If I only want a fast randomized ordered set, treap is usually simpler. Splay becomes attractive when access-based restructuring or sequence-style operations matter.
Core Idea
Every access ends by splaying the touched node to the root. That means repeatedly rotating it upward until it reaches the top.
The local cases are:
zig: the node has a parent but no grandparent,
zig-zig: the node and parent are on the same side,
zig-zag: the node and parent are on opposite sides.
The inorder order never changes, so BST correctness survives every rotation.
Key Insight
The point of splaying is not just ``move this node to the root''. The point is that deep accesses are exactly the expensive ones, so a costly access spends its work reshaping the tree to make related future accesses cheaper.
That is the readable version of the amortized idea. The formal proof uses the access lemma and a potential function, but the operational takeaway is simpler:
recently touched nodes move upward,
long searched paths get reorganized aggressively,
repeated accesses to nearby keys often become much cheaper.
Operations / Main Technique
For an ordered-set splay tree, the usual primitives are:
rotate(x),
splay(x),
find(key),
insert(key),
erase(key),
split(root, key) and merge(left, right),
kth(k) if subtree sizes are stored.
Sequence operations.
Once subtree sizes and lazy tags are added, the same structure can support:
split by position instead of by key,
reverse a segment,
cut one segment and paste it elsewhere,
maintain range sums or other aggregates.
That is a big reason splay trees remain relevant in advanced CP. They are not only search trees; they are flexible sequence containers.
Correctness Intuition
Every rotation preserves inorder order, so the BST property stays intact. Subtree sizes and aggregates remain correct as long as each rotation updates the affected nodes in the right order.
The deeper statement is the amortized bound. One splay can certainly cost \(O(n)\), but those bad cases happen exactly when a deep path is being shortened dramatically. The access lemma formalizes that the total restructuring cost can be charged against a potential that drops over time.
I do not try to remember the full proof in a contest. I remember the engineering rule: a single operation can be ugly, but a long sequence is cheap enough.
Complexity Analysis
search, insert, erase, split, merge: \(O(\log n)\) amortized,
one individual operation: up to \(O(n)\) worst case,
memory: \(O(n)\).
That ``amortized, not worst-case'' distinction matters. It is the main conceptual difference from treaps or AVL-like trees.
Implementation
The reference code keeps the ordered-set version with:
parent pointers,
two children per node,
subtree size,
splay, insert, erase, split, merge, and kth.
That base is intentionally smaller than a full implicit splay. I would rather trust a compact ordered-set core first, then add lazy tags and positional splits once the rotations are already reliable.
Common Pitfalls
Forgetting one parent-pointer update during rotation.
Pulling subtree sizes in the wrong order after structural changes.
Splaying the wrong node after a failed search.
Expecting worst-case \(O(\log n)\) instead of amortized \(O(\log n)\).
Building link-cut trees on top of a splay implementation that is only ``mostly correct''.
Variants / Extensions
implicit splay for sequence manipulation,
lazy propagation for reverse, add, assign, and affine updates,
augmented ordered sets with subtree sums or counts,
link-cut trees, where each auxiliary tree is a splay tree.
Compared with treap.
Treaps are randomized and usually simpler to write. Splay trees are deterministic, amortized, and more delicate, but they are better suited when access restructuring itself is useful or when the same machinery must support link-cut trees.
Practice Problems
Ordered set with insert, erase, predecessor, successor, and k-th queries.
Sequence cut-and-paste problems after upgrading to an implicit splay.
Dynamic tree problems once the splay core feels completely trustworthy.
References
Code
Contest-ready reference implementation for the idea explained above.
struct SplayTree {
struct Node {
int key, sz;
Node *p, *ch[2];
explicit Node(int key_) : key(key_), sz(1), p(nullptr), ch{nullptr, nullptr} {}
};
using Ptr = Node*;
Ptr root = nullptr;
static int size(Ptr x) { return x ? x->sz : 0; }
static void pull(Ptr x) {
if (!x) return;
x->sz = 1 + size(x->ch[0]) + size(x->ch[1]);
}
static bool is_right_child(Ptr x) {
return x->p && x->p->ch[1] == x;
}
void connect(Ptr parent, Ptr child, int dir) {
if (parent) parent->ch[dir] = child;
if (child) child->p = parent;
}
void rotate(Ptr x) {
Ptr p = x->p;
Ptr g = p->p;
int dx = is_right_child(x);
Ptr b = x->ch[dx ^ 1];
if (g) g->ch[g->ch[1] == p] = x;
x->p = g;
connect(p, b, dx);
connect(x, p, dx ^ 1);
pull(p);
pull(x);
if (!x->p) root = x;
}
void splay(Ptr x) {
if (!x) return;
while (x->p) {
Ptr p = x->p;
Ptr g = p->p;
if (!g) {
rotate(x);
} else if ((g->ch[0] == p) == (p->ch[0] == x)) {
rotate(p);
rotate(x);
} else {
rotate(x);
rotate(x);
}
}
root = x;
}
Ptr find_node(int key) {
Ptr cur = root;
Ptr last = nullptr;
while (cur && cur->key != key) {
last = cur;
cur = cur->ch[key > cur->key];
}
splay(cur ? cur : last);
return root && root->key == key ? root : nullptr;
}
bool contains(int key) {
return find_node(key) != nullptr;
}
void insert(int key) {
if (!root) {
root = new Node(key);
return;
}
Ptr cur = root;
while (true) {
if (key == cur->key) {
splay(cur);
return;
}
int dir = key > cur->key;
if (!cur->ch[dir]) {
cur->ch[dir] = new Node(key);
cur->ch[dir]->p = cur;
splay(cur->ch[dir]);
return;
}
cur = cur->ch[dir];
}
}
int kth(int k) {
Ptr cur = root;
while (cur) {
int left_size = size(cur->ch[0]);
if (k == left_size + 1) {
splay(cur);
return cur->key;
}
if (k <= left_size) cur = cur->ch[0];
else {
k -= left_size + 1;
cur = cur->ch[1];
}
}
throw runtime_error("k is out of range");
}
void erase(int key) {
Ptr target = find_node(key);
if (!target) return;
Ptr left = target->ch[0];
Ptr right = target->ch[1];
if (left) left->p = nullptr;
if (right) right->p = nullptr;
delete target;
if (!left) {
root = right;
return;
}
root = left;
Ptr cur = root;
while (cur->ch[1]) cur = cur->ch[1];
splay(cur);
root->ch[1] = right;
if (right) right->p = root;
pull(root);
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.