Introduction to Splay Trees

Introduction

Imagine a library where the librarian automatically moves every book you request to the front shelf. Borrow the same novel twice this week and it is right there waiting for you. Request a book you haven't touched in years and it comes from the back — but now it sits up front too, ready for next time.

That is precisely how a splay tree works. Invented in 1985 by Daniel Sleator and Robert Tarjan, it is a binary search tree with one extra rule: after every search, insertion, or deletion, the touched key is moved to the root via a sequence of tree rotations called a splay.

There are no balance bits, no height counters, no colors. The tree restructures itself lazily, based entirely on what you actually look up. The payoff is elegant: if you access n keys in any order, the total cost is $O(n \log n)$ — as if the tree had been perfectly balanced all along.

This is amortized analysis at its finest. Individual operations can take $O(n)$ in the worst case, but the pain is always spread so thinly across future cheap operations that the average never hurts you. The formal proof relies on a potential function called the access lemma — a clever bookkeeping trick that charges each rotation against an imaginary bank account stored in the nodes themselves.

Hot Keys Float to the Root

The tree below holds keys 1–15. Click any key to splay it: the tree performs zig, zig-zig, and zig-zag rotations until that key sits at the root. Access the same key repeatedly and notice how it stays near the top — the tree has learned it is popular.

<p class="hint">Click any node to <b>splay</b> it to the root. The tree rotates until that key sits at the top. Access the same key repeatedly and watch it stay near the root — the tree learns it is popular.</p>
<div id="tree-wrap">
  <svg id="tree-svg" width="560" height="260" viewBox="0 0 560 260"></svg>
</div>
<div class="status" id="status">Click a node to splay it.</div>
<div class="btns">
  <button id="reset" type="button" class="ghost">Reset tree</button>
  <button id="seq" type="button">Access 1, 1, 1, 8, 8, 15</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#tree-wrap { width: 100%; overflow-x: auto; }
#tree-svg { display: block; }
.edge { stroke: #adb1b8; stroke-width: 1.5; fill: none; }
.node circle { stroke-width: 2; cursor: pointer; transition: r .15s; }
.node circle.cold { fill: #c9ccd1; stroke: #adb1b8; }
.node circle.warm { fill: #f4a261; stroke: #e07b3c; }
.node circle.hot  { fill: #e63946; stroke: #c92f3c; }
.node circle:hover { r: 18; }
.node text { font: 700 13px ui-monospace, monospace; fill: #1d3557; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.node circle.hot ~ text  { fill: #fff; }
.node circle.warm ~ text { fill: #fff; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0 .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Splay tree demo — vanilla JS, no imports.
// Nodes hold: key, left, right, parent.  The splay() method brings a node to root via zig, zig-zig (same side) and zig-zag (opposite side) rotations.
// Heat tracks access frequency so we can colour cold/warm/hot nodes.

// ── BST node ─────────────────────────────────────────────────────────────────
function Node(key){ this.key=key; this.left=this.right=this.parent=null; this.heat=0; }

// ── Splay tree ────────────────────────────────────────────────────────────────
var root = null;

function setParent(node, par){ if(node) node.parent = par; }

function rotateRight(x){
  var y = x.left; if(!y) return;
  x.left = y.right; setParent(y.right, x);
  y.parent = x.parent;
  if(!x.parent) root = y;
  else if(x === x.parent.left) x.parent.left = y;
  else x.parent.right = y;
  y.right = x; x.parent = y;
}
function rotateLeft(x){
  var y = x.right; if(!y) return;
  x.right = y.left; setParent(y.left, x);
  y.parent = x.parent;
  if(!x.parent) root = y;
  else if(x === x.parent.left) x.parent.left = y;
  else x.parent.right = y;
  y.left = x; x.parent = y;
}

function splay(x){
  while(x.parent){
    var p = x.parent, g = p.parent;
    if(!g){
      // zig
      if(x === p.left) rotateRight(p); else rotateLeft(p);
    } else if(x === p.left && p === g.left){
      // zig-zig left
      rotateRight(g); rotateRight(p);
    } else if(x === p.right && p === g.right){
      // zig-zig right
      rotateLeft(g); rotateLeft(p);
    } else if(x === p.left && p === g.right){
      // zig-zag
      rotateRight(p); rotateLeft(g);
    } else {
      // zig-zag
      rotateLeft(p); rotateRight(g);
    }
  }
  root = x;
}

function insert(key){
  var n = new Node(key);
  if(!root){ root = n; return; }
  var cur = root, par = null;
  while(cur){ par = cur; if(key < cur.key) cur = cur.left; else cur = cur.right; }
  n.parent = par;
  if(key < par.key) par.left = n; else par.right = n;
}

function find(key){
  var cur = root;
  while(cur){ if(key === cur.key) return cur; cur = key < cur.key ? cur.left : cur.right; }
  return null;
}

// ── Build initial tree by inserting 1..15 in order (gives a right-leaning chain, which makes the first splay dramatic). ─────────────────────────────────────
function buildTree(){
  root = null;
  // Insert in a shuffled order to get a reasonable starting shape
  var keys = [8,4,12,2,6,10,14,1,3,5,7,9,11,13,15];
  keys.forEach(function(k){ insert(k); });
  // Reset heat
  var n = find(8); // touch root area
}

// ── Access: splay the node and increase its heat ──────────────────────────────
function access(key, skipRender){
  var n = find(key);
  if(!n) return;
  splay(n);
  n.heat = Math.min(n.heat + 1, 5);
  if(!skipRender) render(key);
  return n;
}

// ── Heat class ────────────────────────────────────────────────────────────────
function heatClass(h){ if(h >= 3) return 'hot'; if(h >= 1) return 'warm'; return 'cold'; }

// ── Layout: in-order traversal assigns x positions; depth gives y ─────────────
var SVG_W = 560, SVG_H = 260, RADIUS = 15, LEVEL_H = 52;

function layout(node, depth, counter){
  if(!node) return;
  layout(node.left,  depth+1, counter);
  node._x = (counter[0]++) * (SVG_W / 16) + (SVG_W / 32);
  node._y = depth * LEVEL_H + 28;
  layout(node.right, depth+1, counter);
}

function svgEl(tag, attrs){
  var el = document.createElementNS('http://www.w3.org/2000/svg', tag);
  Object.keys(attrs).forEach(function(k){ el.setAttribute(k, attrs[k]); });
  return el;
}

function render(splayed){
  layout(root, 0, [0]);
  var svg = document.getElementById('tree-svg');
  svg.innerHTML = '';

  // Draw edges first
  function drawEdges(node){
    if(!node) return;
    if(node.left){
      svg.appendChild(svgEl('line',{class:'edge',x1:node._x,y1:node._y,x2:node.left._x,y2:node.left._y}));
      drawEdges(node.left);
    }
    if(node.right){
      svg.appendChild(svgEl('line',{class:'edge',x1:node._x,y1:node._y,x2:node.right._x,y2:node.right._y}));
      drawEdges(node.right);
    }
  }
  drawEdges(root);

  // Draw nodes
  function drawNodes(node){
    if(!node) return;
    var g = svgEl('g',{class:'node','data-key':node.key});
    var cls = heatClass(node.heat);
    var isSplayed = (node.key === splayed);
    var r = isSplayed ? 17 : 14;
    var c = svgEl('circle',{cx:node._x,cy:node._y,r:r,class:cls+(isSplayed?' splayed':'')});
    var t = svgEl('text',{x:node._x,y:node._y}); t.textContent = node.key;
    g.appendChild(c); g.appendChild(t);
    g.addEventListener('click', function(){ onAccess(node.key); });
    svg.appendChild(g);
    drawNodes(node.left);
    drawNodes(node.right);
  }
  drawNodes(root);
}

function onAccess(key){
  var n = find(key);
  access(key);
  var hc = heatClass(root.heat);
  var label = hc==='hot' ? fmt('🔥 Hot key %key% is at the root!', { key: key }) : hc==='warm' ? fmt('Warm key %key% splayed to root.', { key: key }) : fmt('Key %key% splayed to root.', { key: key });
  var s = document.getElementById('status');
  s.textContent = label;
  s.className = 'status ok';
}

document.getElementById('reset').addEventListener('click', function(){
  buildTree();
  render(null);
  document.getElementById('status').textContent = 'Tree reset. Click a node to splay it.';
  document.getElementById('status').className = 'status';
});

document.getElementById('seq').addEventListener('click', function(){
  var seq = [1,1,1,8,8,15];
  var i = 0;
  function step(){
    if(i >= seq.length){ render(seq[seq.length-1]);
      document.getElementById('status').textContent = 'Done! Key 1 is hot (red), key 8 is warm, key 15 just splayed.';
      document.getElementById('status').className = 'status ok';
      return;
    }
    access(seq[i], true);
    i++;
    setTimeout(step, 320);
  }
  buildTree();
  step();
});

buildTree();
render(null);
document.getElementById('status').textContent = 'Click a node to splay it.';

<p class="hint">Click any node to <b>splay</b> it to the root. The tree rotates until that key sits at the top. Access the same key repeatedly and watch it stay near the root — the tree learns it is popular.</p>
<div id="tree-wrap">
  <svg id="tree-svg" width="560" height="260" viewBox="0 0 560 260"></svg>
</div>
<div class="status" id="status">Click a node to splay it.</div>
<div class="btns">
  <button id="reset" type="button" class="ghost">Reset tree</button>
  <button id="seq" type="button">Access 1, 1, 1, 8, 8, 15</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#tree-wrap { width: 100%; overflow-x: auto; }
#tree-svg { display: block; }
.edge { stroke: #adb1b8; stroke-width: 1.5; fill: none; }
.node circle { stroke-width: 2; cursor: pointer; transition: r .15s; }
.node circle.cold { fill: #c9ccd1; stroke: #adb1b8; }
.node circle.warm { fill: #f4a261; stroke: #e07b3c; }
.node circle.hot  { fill: #e63946; stroke: #c92f3c; }
.node circle:hover { r: 18; }
.node text { font: 700 13px ui-monospace, monospace; fill: #1d3557; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.node circle.hot ~ text  { fill: #fff; }
.node circle.warm ~ text { fill: #fff; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0 .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Splay tree demo — vanilla JS, no imports.
// Nodes hold: key, left, right, parent.  The splay() method brings a node to root via zig, zig-zig (same side) and zig-zag (opposite side) rotations.
// Heat tracks access frequency so we can colour cold/warm/hot nodes.

// ── BST node ─────────────────────────────────────────────────────────────────
function Node(key){ this.key=key; this.left=this.right=this.parent=null; this.heat=0; }

// ── Splay tree ────────────────────────────────────────────────────────────────
var root = null;

function setParent(node, par){ if(node) node.parent = par; }

function rotateRight(x){
  var y = x.left; if(!y) return;
  x.left = y.right; setParent(y.right, x);
  y.parent = x.parent;
  if(!x.parent) root = y;
  else if(x === x.parent.left) x.parent.left = y;
  else x.parent.right = y;
  y.right = x; x.parent = y;
}
function rotateLeft(x){
  var y = x.right; if(!y) return;
  x.right = y.left; setParent(y.left, x);
  y.parent = x.parent;
  if(!x.parent) root = y;
  else if(x === x.parent.left) x.parent.left = y;
  else x.parent.right = y;
  y.left = x; x.parent = y;
}

function splay(x){
  while(x.parent){
    var p = x.parent, g = p.parent;
    if(!g){
      // zig
      if(x === p.left) rotateRight(p); else rotateLeft(p);
    } else if(x === p.left && p === g.left){
      // zig-zig left
      rotateRight(g); rotateRight(p);
    } else if(x === p.right && p === g.right){
      // zig-zig right
      rotateLeft(g); rotateLeft(p);
    } else if(x === p.left && p === g.right){
      // zig-zag
      rotateRight(p); rotateLeft(g);
    } else {
      // zig-zag
      rotateLeft(p); rotateRight(g);
    }
  }
  root = x;
}

function insert(key){
  var n = new Node(key);
  if(!root){ root = n; return; }
  var cur = root, par = null;
  while(cur){ par = cur; if(key < cur.key) cur = cur.left; else cur = cur.right; }
  n.parent = par;
  if(key < par.key) par.left = n; else par.right = n;
}

function find(key){
  var cur = root;
  while(cur){ if(key === cur.key) return cur; cur = key < cur.key ? cur.left : cur.right; }
  return null;
}

// ── Build initial tree by inserting 1..15 in order (gives a right-leaning chain, which makes the first splay dramatic). ─────────────────────────────────────
function buildTree(){
  root = null;
  // Insert in a shuffled order to get a reasonable starting shape
  var keys = [8,4,12,2,6,10,14,1,3,5,7,9,11,13,15];
  keys.forEach(function(k){ insert(k); });
  // Reset heat
  var n = find(8); // touch root area
}

// ── Access: splay the node and increase its heat ──────────────────────────────
function access(key, skipRender){
  var n = find(key);
  if(!n) return;
  splay(n);
  n.heat = Math.min(n.heat + 1, 5);
  if(!skipRender) render(key);
  return n;
}

// ── Heat class ────────────────────────────────────────────────────────────────
function heatClass(h){ if(h >= 3) return 'hot'; if(h >= 1) return 'warm'; return 'cold'; }

// ── Layout: in-order traversal assigns x positions; depth gives y ─────────────
var SVG_W = 560, SVG_H = 260, RADIUS = 15, LEVEL_H = 52;

function layout(node, depth, counter){
  if(!node) return;
  layout(node.left,  depth+1, counter);
  node._x = (counter[0]++) * (SVG_W / 16) + (SVG_W / 32);
  node._y = depth * LEVEL_H + 28;
  layout(node.right, depth+1, counter);
}

function svgEl(tag, attrs){
  var el = document.createElementNS('http://www.w3.org/2000/svg', tag);
  Object.keys(attrs).forEach(function(k){ el.setAttribute(k, attrs[k]); });
  return el;
}

function render(splayed){
  layout(root, 0, [0]);
  var svg = document.getElementById('tree-svg');
  svg.innerHTML = '';

  // Draw edges first
  function drawEdges(node){
    if(!node) return;
    if(node.left){
      svg.appendChild(svgEl('line',{class:'edge',x1:node._x,y1:node._y,x2:node.left._x,y2:node.left._y}));
      drawEdges(node.left);
    }
    if(node.right){
      svg.appendChild(svgEl('line',{class:'edge',x1:node._x,y1:node._y,x2:node.right._x,y2:node.right._y}));
      drawEdges(node.right);
    }
  }
  drawEdges(root);

  // Draw nodes
  function drawNodes(node){
    if(!node) return;
    var g = svgEl('g',{class:'node','data-key':node.key});
    var cls = heatClass(node.heat);
    var isSplayed = (node.key === splayed);
    var r = isSplayed ? 17 : 14;
    var c = svgEl('circle',{cx:node._x,cy:node._y,r:r,class:cls+(isSplayed?' splayed':'')});
    var t = svgEl('text',{x:node._x,y:node._y}); t.textContent = node.key;
    g.appendChild(c); g.appendChild(t);
    g.addEventListener('click', function(){ onAccess(node.key); });
    svg.appendChild(g);
    drawNodes(node.left);
    drawNodes(node.right);
  }
  drawNodes(root);
}

function onAccess(key){
  var n = find(key);
  access(key);
  var hc = heatClass(root.heat);
  var label = hc==='hot' ? fmt('🔥 Hot key %key% is at the root!', { key: key }) : hc==='warm' ? fmt('Warm key %key% splayed to root.', { key: key }) : fmt('Key %key% splayed to root.', { key: key });
  var s = document.getElementById('status');
  s.textContent = label;
  s.className = 'status ok';
}

document.getElementById('reset').addEventListener('click', function(){
  buildTree();
  render(null);
  document.getElementById('status').textContent = 'Tree reset. Click a node to splay it.';
  document.getElementById('status').className = 'status';
});

document.getElementById('seq').addEventListener('click', function(){
  var seq = [1,1,1,8,8,15];
  var i = 0;
  function step(){
    if(i >= seq.length){ render(seq[seq.length-1]);
      document.getElementById('status').textContent = 'Done! Key 1 is hot (red), key 8 is warm, key 15 just splayed.';
      document.getElementById('status').className = 'status ok';
      return;
    }
    access(seq[i], true);
    i++;
    setTimeout(step, 320);
  }
  buildTree();
  step();
});

buildTree();
render(null);
document.getElementById('status').textContent = 'Click a node to splay it.';

Result

Console

Notice the asymmetry. A single access can trigger a long chain of rotations — $O(n)$ in the worst case. But after that reorganization, all the keys you passed through on the way up are now shallower. The tree has paid a large upfront cost and then pre-cached the neighborhood. The access lemma proves that any sequence of $m$ operations on an $n$ -key splay tree costs at most $O((m + n) \log n)$ total — so the amortized cost per operation is $O(\log n)$ .

The Real Complexity

How fast is a splay tree, really?

Worst-case per operation: $O(n)$ . If you access the deepest leaf in a maximally unbalanced tree, the splay drags it all the way to the root through $n-1$ rotations.
Amortized per operation: $O(\log n)$ . This is the result of the access lemma proved by Sleator and Tarjan in 1985. They assign each node $x$ a rank $r(x) = \log(\text{size of the subtree rooted at } x)$ and define the potential $\Phi = \sum_x r(x)$ . Each splay step that restructures the tree releases potential, paying for the rotations performed. The algebra shows the total cost across any sequence of $m$ splays is $O((m + n) \log n)$ .
Working-set property (proven): if a key has not been accessed for $t$ steps, the next access costs $O(\log t)$ . Hot keys are genuinely faster.
Dynamic finger property (proven): accessing a key at distance $d$ from the previous access costs $O(\log d)$ .
Dynamic optimality conjecture (open): Sleator and Tarjan conjectured that splay trees are optimally efficient among all dynamic BSTs — no other algorithm can be more than a constant factor faster on any sequence of accesses. This remains one of the most famous open problems in data-structure theory, connecting to the P vs NP spirit of asking what is fundamentally optimal.

The contrast between the ugly $O(n)$ worst case and the beautiful $O(\log n)$ amortized guarantee is the whole point. Splay trees trade certainty per operation for certainty across operations — and the trade is provably fair.

Where It Matters

"Some keys are hot, most are cold" describes almost every real workload — and splay trees are purpose-built for that shape:

Caches and working sets: operating systems and databases frequently access a small subset of data. Splay trees automatically keep that subset near the root, mimicking an LRU cache without extra bookkeeping.
Network routing tables: routing software accesses popular destination prefixes far more often than obscure ones. A splay tree keeps common routes fast.
Garbage-collected runtimes: the GC in several language runtimes (including a well-known C++ STL implementation by SGI) uses splay trees for free-list management because short-lived allocations dominate.
Persistent data structures: because splay trees only use rotations (no recoloring), they compose cleanly with path-copying techniques for functional or persistent variants.
Teaching amortized analysis: splay trees are the canonical example in algorithms courses for potential-function arguments. If you understand the access lemma, you understand amortized analysis. Compare how dynamic shortest paths also exploits lazy restructuring to spread cost.

The deeper lesson is that the shape of a data structure need not be fixed at build time. Splay trees let the access pattern itself design the tree — a form of self-organization that shows up across all of computer science.

Conclusion

Splay trees carry a beautiful paradox: they have no balance invariant, yet they stay balanced in aggregate. Each access can cost $O(n)$ , yet over any sequence the average is $O(\log n)$ . No metadata, no colors, no heights — just rotations guided by what you actually access.

The formal guarantee comes from the access lemma, one of the cleanest applications of potential-function analysis in all of computer science. And behind that guarantee lurks an open problem that has stood for four decades: is the splay tree dynamically optimal? No one knows whether another BST strategy can beat it by more than a constant. Until that question is answered, splay trees remain both a practical tool and a theoretical mystery — and every key you access is a small experiment in the art of self-organization.

Comments

Loading comments...

https://www.kipuhub.com/en/article/splay-trees/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Splay Trees

When every lookup rebalances the tree