Splay tree

A splay tree is a self-adjusting binary search tree introduced by Sleator and Tarjan^[1]. It stores no colours, heights or sizes. Every search, insertion or deletion ends by splaying: rotating the accessed node, or the last node on the search path, up to the root. The tree can become arbitrarily unbalanced, but splaying roughly halves the depth of every node on the path it follows, and an amortized analysis shows that the expensive accesses pay for themselves^[1]^[5].

§ 01

Splaying

Splaying moves a node $x$ up two levels at a time. If $x$ and its parent $y$ are both left children, or both right children, the zig-zig step rotates $y$ over the grandparent $z$ and then $x$ over $y$ . If one is a left child and the other a right child, the zig-zag step rotates $x$ over $y$ and then over $z$ . A final single rotation, zig, is used when $x$ is a child of the root^[1].

The zig-zig step. Rotating the grandparent first is what distinguishes splaying from simply rotating x to the root, and is what makes the amortized bound hold.

Rotating the grandparent first in the zig-zig case is essential. Rotating $x$ up one level at a time would also bring it to the root, but a path would stay a path, and accessing its nodes in order could cost $Θ (n)$ each.

A functional splay tree in OCaml: splay returns the new tree, with a counter for rotations.

type t = Leaf | Node of t * int * t
 
let rotations = ref 0
 
(* Bring x, or the last node on the search path to it, to the root. *)
let rec splay x t =
  match t with
  | Leaf -> Leaf
  | Node (l, y, r) when x = y -> t
  | Node (l, y, r) when x < y -> (
      match l with
      | Leaf -> t
      | Node (ll, z, lr) when x = z -> incr rotations; Node (ll, z, Node (lr, y, r))  (* zig *)
      | Node (ll, z, lr) when x < z -> (
          match splay x ll with
          | Leaf -> incr rotations; Node (ll, z, Node (lr, y, r))
          | Node (a, w, b) ->  (* zig-zig *)
              rotations := !rotations + 2; Node (a, w, Node (b, z, Node (lr, y, r))))
      | Node (ll, z, lr) -> (
          match splay x lr with
          | Leaf -> incr rotations; Node (ll, z, Node (lr, y, r))
          | Node (a, w, b) ->  (* zig-zag *)
              rotations := !rotations + 2; Node (Node (ll, z, a), w, Node (b, y, r))))
  | Node (l, y, r) -> (
      match r with
      | Leaf -> t
      | Node (rl, z, rr) when x = z -> incr rotations; Node (Node (l, y, rl), z, rr)
      | Node (rl, z, rr) when x > z -> (
          match splay x rr with
          | Leaf -> incr rotations; Node (Node (l, y, rl), z, rr)
          | Node (a, w, b) ->
              rotations := !rotations + 2; Node (Node (Node (l, y, rl), z, a), w, b))
      | Node (rl, z, rr) -> (
          match splay x rl with
          | Leaf -> incr rotations; Node (Node (l, y, rl), z, rr)
          | Node (a, w, b) ->
              rotations := !rotations + 2; Node (Node (l, y, a), w, Node (b, z, rr))))
 
let insert x t =
  match splay x t with
  | Leaf -> Node (Leaf, x, Leaf)
  | Node (l, y, r) as t ->
      if x = y then t
      else if x < y then Node (l, x, Node (Leaf, y, r))
      else Node (Node (l, y, Leaf), x, r)
 
let mem x t = match splay x t with Node (_, y, _) as t -> (x = y, t) | Leaf -> (false, Leaf)

A degenerate tree, and the cost of accesses on it.

open Splay
 
let rec height = function Leaf -> 0 | Node (l, _, r) -> 1 + max (height l) (height r)
 
let n = 1023

Running it.

after inserting 1..1023 in order: height 1023
access    1: 1022 rotations, height now 513
access    2:  511 rotations, height now 258
access    3:  257 rotations, height now 132
access  512:   67 rotations, height now 69
accessing 1..1023 in order: 3509 rotations
100,000 random accesses: 1145880 rotations, 11.5 per access

Inserting keys in increasing order leaves a path of 1023 nodes. Accessing the deepest key costs 1022 rotations, but leaves the tree about half as tall, and a few more accesses bring the height down to tens. Accessing all keys in order then costs 3.4 rotations each, and random accesses about 11.5, close to $lo g_{2} 1023 \approx 10$ .

§ 02

Amortized bounds

Give each node the potential $lo g_{2} s (v)$ , where $s (v)$ is the size of its subtree, and let $Φ$ be the sum over all nodes. Sleator and Tarjan's access lemma states that splaying $x$ in a tree with root $t$ has amortized cost^[1]^[5]

3 (lo g_{2} s (t) - lo g_{2} s (x)) + 1 = O (lo g n)

Many stronger properties follow. Static optimality: splay trees are within a constant factor of the best static tree for any access frequencies. Accessing all keys in order takes linear time in total^[2], and accessing a key close in order to the previous one is cheap^[3]. Whether splay trees are within a constant factor of every other binary search tree algorithm on every access sequence, the dynamic optimality conjecture, is open^[1].

Splaying modifies the tree even on a lookup, so a functional splay tree must return the new tree from every operation, as above. Since the bounds are amortized, a persistent use that repeats an expensive access on an old version loses them. Okasaki's splay heaps use only the partitioning step of splaying and make a fast functional priority queue^[4].

§ 03

History

Daniel Sleator and Robert Tarjan introduced splay trees in 1985^[1]. Tarjan proved the sequential access theorem the same year^[2], and Cole proved the dynamic finger theorem in 2000^[3].