AVL and
red-black trees both bound height by enforcing an
invariant after every write — a height number kept within 1, or a set of color rules — so that
every single operation, not just most of them, is guaranteed O(log n). A splay
tree gives that up entirely: it enforces no shape invariant at all, and a single unlucky operation
can legitimately cost O(n). What it offers instead is a different kind of guarantee —
amortized, not worst-case — earned by doing one extra thing on every insert, search, and
delete: whichever node was just touched gets rotated all the way up to become the new root, via a
sequence of paired rotations called splaying. Access something once and it's
expensive to reach; access it again immediately after and it's O(1), because it's
sitting at the root. That bet — that whatever was just used is likely to be used again soon — is the
same principle an LRU cache runs on, just paid for with tree rotations instead of a linked list.
The tree below was loaded by inserting 1 through 7 in ascending order, the same sequence the AVL and red-black pages used — and here it lands somewhere neither of those trees would ever allow: a full linear chain, height 7, checked against the shipped algorithm below. That's not a bug — inserting a new maximum always attaches it as the current root's right child with nothing else nearby, so its splay is always a single "zig" rotation, never the tree-collapsing "zig-zig" case — it's the honest cost of having no balance invariant at all. Try searching for 4 now and watch it splay to the root: the walk down touches every node in the chain, but the splay back up collapses the whole thing, and the tree's height drops from 7 to 4 in that one operation (also checked below, not just eyeballed). Insert attaches a new value as a leaf and splays it up the same way; inserting an already-present value still splays the existing node to the root instead of silently no-oping, since a duplicate lookup is itself an access. Delete splays the target to the root, removes it, then joins its two subtrees by splaying the left subtree's maximum to its own top and hanging the right subtree off its (now guaranteed-empty) right side — that join step only has real work to do when the left subtree isn't itself already a plain chain (deleting straight from the loaded chain never needs one, checked: every value's left subtree comes out chainless). After searching 4 as suggested above, try deleting 6 to see a real one: the join logs its own separate splay, rotating 5 up to become the left subtree's new top before the right side reattaches.
Splaying a node x to the root repeats one of three moves, chosen by looking at
x's parent and grandparent together, until x has no parent left:
x's parent is the root (no grandparent). One rotation at
the parent, in the direction that brings x up. This is the terminal step, always the
last one performed, and (as the loaded demo above shows) the only step a splay ever needs
when the accessed node is one level deep.x and its parent are both left children, or both right
children (a straight line, three nodes in a row). Rotate the grandparent first, then the
parent — both in the same direction. Rotating in the other order (parent first, then
grandparent) also legally moves x to the top of that three-node span, but produces a
different final shape, and that difference is exactly what the amortized guarantee depends on (see
Pitfalls).x is a right child and its parent is a left child, or
the mirror (a bent shape). Rotate at the parent first — in the direction that straightens
x out from under it — then rotate at the grandparent, in the other direction.Zig-zig, x and p both left children (mirror handles both-right):
gp p x
/ / \ / \
p --> x gp --> A p
/ / \ / \
x A B B gp
/ \ / \
A B C D
(rotate at gp first) (rotate at p second)
Zig-zag, x a right child, p a left child (mirror handles the other diagonal):
gp gp x
/ / / \
p --> x --> p gp
\ / \ / \ / \
x p C A B C D
/ \ / \
B C A B
(rotate at p first) (rotate at gp second)Both multi-step cases rotate the node two levels up per pass instead of one — that's
what makes splaying to the root take at most ⌈depth / 2⌉ passes, and it's also the
mechanical reason zig-zig's rotation order matters: rotating grandparent-then-parent (shown above)
roughly halves the depth of everything x passes on the way up, where rotating
parent-then-grandparent first (the "naive" move-to-root strategy) does not — see Pitfalls for a
checked, measured comparison.
Search walks down like an ordinary BST search, then splays whatever node it last touched — the found node on a hit, or the node it fell off the tree from on a miss — to the root either way. Splaying on a miss is a deliberate, standard choice, not an oversight: it means a repeated search for the same absent value stays cheap (the node nearest to where it would be is already at the root), the same benefit a hit gets.
Insert is an ordinary BST insert — walk down by comparison, attach a new leaf where the walk falls off the tree — followed by splaying that new leaf to the root. If the value already exists, nothing is attached; the existing node is splayed instead, per the "any access counts" rule above.
Delete splays the target to the root first (same fall-off convention as search if it's missing, in which case nothing more happens), then removes it by joining its two subtrees: detach the left subtree, walk to its maximum, splay that node to the top of the left subtree alone — which leaves it with no right child, since it was already the largest value there — then attach the original right subtree as its new right child. The order matters: splaying the join node before reattaching the right subtree means that second splay only ever walks within the left subtree, never touching (or needing to be careful about) the right one at all.
class SplayTree {
#root = null;
#rotateLeft(x) {
const y = x.right;
x.right = y.left;
if (y.left !== null) y.left.parent = x;
y.parent = x.parent;
if (x.parent === null) this.#root = y;
else if (x === x.parent.left) x.parent.left = y;
else x.parent.right = y;
y.left = x;
x.parent = y;
}
#rotateRight(x) {
const y = x.left;
x.left = y.right;
if (y.right !== null) y.right.parent = x;
y.parent = x.parent;
if (x.parent === null) this.#root = y;
else if (x === x.parent.right) x.parent.right = y;
else x.parent.left = y;
y.right = x;
x.parent = y;
}
#splay(x) {
while (x.parent !== null) {
const p = x.parent, gp = p.parent;
if (gp === null) { // zig
if (x === p.left) this.#rotateRight(p); else this.#rotateLeft(p);
} else if (p === gp.left && x === p.left) { // zig-zig, left-left
this.#rotateRight(gp); this.#rotateRight(p);
} else if (p === gp.right && x === p.right) { // zig-zig, right-right
this.#rotateLeft(gp); this.#rotateLeft(p);
} else if (p === gp.left && x === p.right) { // zig-zag
this.#rotateLeft(p); this.#rotateRight(gp);
} else { // zig-zag, mirror
this.#rotateRight(p); this.#rotateLeft(gp);
}
}
}
// walks to `value`; returns the node itself if found, else the last node
// visited before falling off the tree (or null, if the tree is empty).
#findLast(value) {
let cur = this.#root, last = null;
while (cur !== null) {
last = cur;
if (value === cur.value) return cur;
cur = value < cur.value ? cur.left : cur.right;
}
return last;
}
insert(value) {
if (this.#root === null) { this.#root = { value, left: null, right: null, parent: null }; return; }
const last = this.#findLast(value);
if (last.value === value) { this.#splay(last); return; } // already present — splay it anyway
const z = { value, left: null, right: null, parent: last };
if (value < last.value) last.left = z; else last.right = z;
this.#splay(z);
}
search(value) {
if (this.#root === null) return false;
const last = this.#findLast(value);
this.#splay(last);
return last.value === value;
}
delete(value) {
if (this.#root === null) return false;
const last = this.#findLast(value);
this.#splay(last);
if (last.value !== value) return false; // splayed the nearest node; nothing removed
if (last.left === null) {
this.#root = last.right;
if (this.#root !== null) this.#root.parent = null;
} else {
const rightSub = last.right;
const leftSub = last.left;
leftSub.parent = null;
let maxNode = leftSub;
while (maxNode.right !== null) maxNode = maxNode.right;
this.#root = leftSub;
this.#splay(maxNode); // splays within the detached left subtree only
maxNode.right = rightSub;
if (rightSub !== null) rightSub.parent = maxNode;
}
return true;
}
contains(value) {
let cur = this.#root;
while (cur !== null) {
if (value === cur.value) return true;
cur = value < cur.value ? cur.left : cur.right;
}
return false;
}
}The interactive demo above uses equivalent insertSplay/searchSplay/
deleteSplay functions with extra bookkeeping to record the descent path and which
rotation(s) fired, purely to drive the highlighting and log text — the algorithm is identical,
including the parent pointers, which (like red-black
tree's fixups) this needs and the plain BST/
AVL pages didn't: identifying the zig-zig/zig-zag case
requires seeing two ancestor levels above x at once.
Verified against a plain JavaScript Set as a reference model across 300 randomized
trials of 40 mixed insert/search/delete operations each on a deliberately small value range (to force
heavy collisions between inserts, duplicate-splays, and deletes of both present and absent values),
checking after every single operation: the BST ordering property, that every node's
parent pointer matches its actual position in the tree (not just that the tree "looks"
right by value — see Pitfalls), that the root's own parent is always null, that
size() matches the Set's size, that contains agrees with the
Set for every value the Set holds, and that a freshly-inserted or
freshly-found value is always the new root — 12,000 operations with zero mismatches, followed by a
full drain (deleting every remaining value) confirming the tree always ends empty. The checker was
self-tested against two deliberately broken variants first: swapping last.left/
last.right on insert (caught immediately — BST property violated) and dropping the
rightSub.parent = maxNode line from delete's join step (caught on the very
first trial's post-op drain — parent pointers inconsistent), before trusting a clean run on the real
code. Re-verified by extracting the exact shipped insertSplay/searchSplay/
deleteSplay functions out of the HTML and re-running an equivalent pass directly against
them, plus a real click-driven fake-DOM harness confirming the two worked examples named above (the
1-through-7 ascending load produces a height-7 chain and searching 4 drops it to height 4; then
deleting 6 from that state logs a separate join-splay). See /tmp/splay/ref.js,
/tmp/splay/test_harness.js, /tmp/splay/broken2.js,
/tmp/splay/broken4.js, /tmp/splay/extracted_trial.js, and
/tmp/splay/fake_dom.js//tmp/splay/click_harness.js, scratch, not
committed.
"Rotate to the root one level at a time" still finds the right answer, but it isn't
splaying, and it quietly loses the whole point of the structure. A single rotation moving
x up past its parent, repeated until x is the root, produces a correct BST
with x at the top every time — it's tempting to write, and every correctness check on
this page (BST order, Set agreement) would pass it. What it doesn't do is the
two-level zig-zig lookahead's actual job: roughly halving the depth of everything on the accessed
path, not just moving one node. Measured, not just claimed: build a fully linear chain of n
nodes (plain descending-order BST insert, no splaying), then access every value once, from the
deepest node to the shallowest — the textbook worst case a self-adjusting tree is supposed to
handle well. At n = 1000, proper zig-zig splaying does 5,374 total
comparison steps across all 1,000 accesses (~5.4 per operation, consistent with
O(log n) amortized); naive single-rotation-per-step "splaying" does
501,499 (~501.5 per operation — growing linearly with n, i.e.
O(n) amortized, exactly the guarantee splaying exists to avoid). The gap only widens
with n: at 2,000 it's 10,804 vs. 2,002,999.
A splay tree can look right by value and still have a corrupted parent pointer.
The mirror image of the red-black delete
pitfall named above: dropping rightSub.parent = maxNode from the join step doesn't
change any node's value, doesn't break the BST ordering, and doesn't make
contains return a wrong answer for the sequence that exposed it — printing the tree by
value looks completely normal. What's actually wrong only shows up by checking the pointer itself:
inserting 5, 3, 8, 2, 4, 7, 9 then deleting 5 leaves node 8's
.parent field pointing at the already-discarded node 5 instead of its real
parent, the new root 4 — invisible to any check that only reads values top-down from
the root, caught here only because the verification above walks the tree and confirms every node's
parent
independently rather than trusting the shape it renders.
No shape invariant means no single-operation guarantee, ever — not "usually fine."
The loaded demo's own height-7 chain from an ascending 1-through-7 insert is the concrete version of
this: a plain unbalanced BST given the same
input produces the identical worst-case shape, and nothing about splaying prevents it, because
splaying only ever touches the single path it just walked — it has no mechanism to notice or fix
imbalance anywhere else in the tree. The amortized bound is a real, provable guarantee over any
sequence of operations, but it says nothing about any one operation in isolation, unlike
AVL or red-black's per-operation O(log n).
splay(1) Linux kernel scheduler class and some LZ77-family
compressors' sliding-window dictionaries have both used splay trees for the same "make the
recently-touched thing cheap to reach again" property — the same intuition an
LRU cache runs on, reached with a tree's ordering
instead of a hash map plus a linked list.Time: insert, search/contains-via-splay,
and delete are all O(log n) amortized over any sequence of
operations — proven with a potential-function argument this page doesn't reproduce — but any single
operation can cost O(n) in the worst case (the loaded demo's height-7 chain makes that
concrete: searching for 1 in it walks all 7 nodes before the splay even starts). This is the
one genuine trade against AVL and
red-black trees, both of which guarantee
O(log n) for every individual operation, not just on average over many. Space:
O(n) for n nodes — two child pointers and one parent pointer each, the
same per-node cost as a red-black tree, minus the one color bit (a splay tree stores no
per-node metadata at all — nothing to update, nothing to get wrong, unlike AVL's height or
red-black's color).
See Choosing a Search Tree for when that amortized bound and skew-friendly behavior beats a per-operation guarantee like AVL or red-black's.