Splay Tree

A splay tree is a self-adjusting BST: every access (search, insert, delete) moves the touched node to the root through a sequence of rotations called "splaying." It has no balance invariants but achieves amortized O(log n) per operation, and recently-accessed keys become very fast (working-set theorem).

Complexity

How it works

Splaying applies one of three rotation patterns — zig (parent is root), zig-zig (same side), zig-zag (different sides) — repeatedly until the target reaches the root. Amortized analysis (Sleator & Tarjan, 1985) shows total cost over m operations is O(m log n) even though individual ops can be O(n).

Python implementation

class Node:
    __slots__ = ("key", "left", "right")
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None


def _rotate_right(x):
    y = x.left; x.left = y.right; y.right = x; return y

def _rotate_left(x):
    y = x.right; x.right = y.left; y.left = x; return y


def splay(root, key):
    """Splay the node with `key` (or last accessed) to the root."""
    if root is None or root.key == key:
        return root
    if key < root.key:
        if root.left is None:
            return root
        if key < root.left.key:
            root.left.left = splay(root.left.left, key)
            root = _rotate_right(root)
        elif key > root.left.key:
            root.left.right = splay(root.left.right, key)
            if root.left.right:
                root.left = _rotate_left(root.left)
        return root if root.left is None else _rotate_right(root)
    else:
        if root.right is None:
            return root
        if key > root.right.key:
            root.right.right = splay(root.right.right, key)
            root = _rotate_left(root)
        elif key < root.right.key:
            root.right.left = splay(root.right.left, key)
            if root.right.left:
                root.right = _rotate_right(root.right)
        return root if root.right is None else _rotate_left(root)


class SplayTree:
    def __init__(self): self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = Node(key); return
        self.root = splay(self.root, key)
        if self.root.key == key: return
        n = Node(key)
        if key < self.root.key:
            n.right = self.root; n.left = self.root.left; self.root.left = None
        else:
            n.left = self.root; n.right = self.root.right; self.root.right = None
        self.root = n


t = SplayTree()
for k in [50, 30, 20, 40, 70, 60, 80]: t.insert(k)
print(t.root.key)   # 80 — last inserted bubbled to the root

Trade-offs

• Amortized O(log n) — individual operations can be slow, but total cost is balanced.
• Recently-accessed keys are near the root — good locality of reference for skewed workloads.
• Not thread-safe by default: every read mutates the tree.
• Used in Linux kernel internals (e.g. older I/O scheduler) and some allocator implementations.

← Back to Algorithms