Splay Tree — Complete Guide

What is Splay Tree?

Splay Tree is a self-balancing binary search tree developed by Daniel Sleator and Robert Tarjan in 1985.

The key idea: every time a node is accessed, it is moved to the root of the tree using a splay operation (a series of rotations). It does not store height, color, or other metadata — only parent/left/right pointers.

Node Structure

class SplayNode:
    def __init__(self, key, value=None):
        self.key    = key
        self.value  = value
        self.left   = None   # left subtree  (keys < key)
        self.right  = None   # right subtree (keys > key)
        self.parent = None   # parent

Primary Operation — Splay

Splay moves node x to the root through three rotation cases:

flowchart TD A[Node X needs to be moved to root] --> B{Is X already root?} B -- Yes --> Z[Done] B -- No --> C{Is Parent P the root?} C -- Yes --> D["Zig: single rotation\n(Left or Right)"] D --> Z C -- No --> E{Are X and P on the same side?} E -- Yes --> F["Zig-Zig: two identical rotations\n(both Left or both Right)"] E -- No --> G["Zig-Zag: two different rotations\n(Left+Right or Right+Left)"] F --> A G --> A

Three Rotation Cases

flowchart LR subgraph ZIG["🔄 ZIG — P is root"] direction TB z1["G — P — X"] -->|"Right Rotate(P)"| z2["X → P → G"] end subgraph ZIGZIG["🔄🔄 ZIG-ZIG — X and P on same side"] direction TB zz1["G → P → X"] -->|"Rotate(G) then Rotate(P)"| zz2["X → P → G"] end subgraph ZIGZAG["↩ī¸â†Ēī¸ ZIG-ZAG — X and P on different sides"] direction TB zzg1["G → P ↘ X"] -->|"Rotate(P) then Rotate(G)"| zzg2["P ← X → G"] end

Step-by-Step Example — Insert + Splay

Inserting keys: 10, 20, 5, 15, 30 and then performing find(5)

After inserting all keys (no balancing):

graph TD A((30)) --> B((15)) B --> C((5)) C --> D((10)) D --> E((20)) style A fill:#e8f4f8,stroke:#2196F3

After find(5) — node 5 moves to the root:

graph TD ROOT((5)) --> L[null] ROOT --> R((30)) R --> RL((15)) RL --> RLL((10)) RLL --> RLLL[null] RLL --> RLLR((20)) RL --> RLR[null] R --> RR[null] style ROOT fill:#4CAF50,color:#fff,stroke:#388E3C style R fill:#e8f4f8,stroke:#2196F3 style RL fill:#e8f4f8,stroke:#2196F3

Application Examples

mindmap root((Splay Tree)) Caching LRU-like caches DNS cache CPU instruction cache Networking IP routing Firewall rule lookup Compilers Symbol tables Scope management Databases Windows NT registry Buffer pool Algorithms Link-Cut Trees Dynamic trees Top trees

Specific Cases

Application Why Splay Tree?
Browser Cache Recently opened URLs are likely needed again → they are at the root
Text Editor Recent edits are local → cursor position is found quickly
Network Router "Hot" IP addresses are constantly at the top
Windows NT Registry Frequently read keys bubble to the top
Garbage Collector (JVM) Searching for free blocks by size
Link-Cut Trees Splay is the building block for dynamic trees

Complexity Table

Operation Worst Case Amortized Best Case
Find O(n) O(log n) O(1)
Insert O(n) O(log n) O(1)
Delete O(n) O(log n) O(1)
Split O(n) O(log n) O(log n)
Merge O(n) O(log n) O(log n)
k-th element O(n) O(log n) O(1)

⚠ī¸ Worst case O(n) for a single operation, but a series of m operations is always ≤ O(m log n)

Key Pros and Cons

✅ Advantages ❌ Disadvantages
Simple implementation Worst-case O(n)
Adapts to access patterns Not for real-time
Excellent cache locality Poor for uniform access
Split/Merge in O(log n) Not persistent
Good for skewed access find modifies the tree

Splay Tree vs B-Tree vs B+Tree

Characteristic Splay Tree B-Tree B+Tree
Structure Binary M-ary M-ary
Data Storage All nodes All nodes Leaves only
Optimization RAM / Cache Disk Disk + Range
Balancing Amortized Strict Strict
Tree Height O(log n) amort. O(log_m n) O(log_m n)
Locality of reference ✅ Excellent ❌ None ❌ None
Range queries ⚠ī¸ Average ⚠ī¸ Average ✅ Excellent
Sequential scan ❌ Poor ⚠ī¸ Average ✅ Excellent
Memory Overhead ✅ Minimal ⚠ī¸ Average ⚠ī¸ Average
Node Metadata ❌ None Degree/count Degree/count
Worst-case 1 op ❌ O(n) ✅ O(log n) ✅ O(log n)
Application Cache, RAM FS, DB Index DBMS, OS

Performance under Different Access Patterns

{
  "title": { "text": "Relative Performance by Access Pattern", "left": "center" },
  "tooltip": { "trigger": "axis", "axisPointer": { "type": "shadow" } },
  "legend": { "top": 30, "data": ["Splay Tree", "B-Tree", "B+Tree"] },
  "xAxis": {
    "type": "category",
    "data": ["Random", "Local (80/20)", "Sequential", "Range Scan", "Stream Insertion"]
  },
  "yAxis": {
    "type": "value",
    "name": "Score (higher = better)",
    "max": 100
  },
  "series": [
    {
      "name": "Splay Tree",
      "type": "bar",
      "data": [55, 95, 30, 45, 60],
      "itemStyle": { "color": "#4CAF50" }
    },
    {
      "name": "B-Tree",
      "type": "bar",
      "data": [75, 65, 70, 70, 75],
      "itemStyle": { "color": "#2196F3" }
    },
    {
      "name": "B+Tree",
      "type": "bar",
      "data": [70, 60, 95, 98, 80],
      "itemStyle": { "color": "#FF9800" }
    }
  ]
}

Implementation — Key Operations (Python)

class SplayTree:

    def _right_rotate(self, x):
        p = x.parent
        b = x.right
        # x goes up, p goes down to the right
        if p.parent:
            if p.parent.left == p: p.parent.left = x
            else:                  p.parent.right = x
        x.parent = p.parent
        x.right  = p
        p.parent = x
        p.left   = b
        if b: b.parent = p

    def _left_rotate(self, x):
        p = x.parent
        b = x.left
        if p.parent:
            if p.parent.left == p: p.parent.left = x
            else:                  p.parent.right = x
        x.parent = p.parent
        x.left   = p
        p.parent = x
        p.right  = b
        if b: b.parent = p

    def splay(self, x):
        while x.parent:                        # until x is root
            p = x.parent
            g = p.parent                       # grandparent
            if not g:
                # Zig
                if p.left == x: self._right_rotate(x)
                else:           self._left_rotate(x)
            elif g.left == p and p.left == x:
                # Zig-Zig (left-left)
                self._right_rotate(p)
                self._right_rotate(x)
            elif g.right == p and p.right == x:
                # Zig-Zig (right-right)
                self._left_rotate(p)
                self._left_rotate(x)
            else:
                # Zig-Zag
                if p.left == x: self._right_rotate(x); self._left_rotate(x)
                else:           self._left_rotate(x);  self._right_rotate(x)
        self.root = x

    def find(self, key):
        node = self.root
        last = None
        while node:
            last = node
            if key == node.key:
                self.splay(node)           # found → move to root
                return node
            elif key < node.key: node = node.left
            else:                node = node.right
        if last: self.splay(last)          # not found → splay the last visited node
        return None

    def insert(self, key, value=None):
        if not self.root:
            self.root = SplayNode(key, value); return
        node = self.root
        while True:
            if key < node.key:
                if not node.left:
                    node.left = SplayNode(key, value)
                    node.left.parent = node
                    self.splay(node.left); return
                node = node.left
            elif key > node.key:
                if not node.right:
                    node.right = SplayNode(key, value)
                    node.right.parent = node
                    self.splay(node.right); return
                node = node.right
            else:
                node.value = value         # update
                self.splay(node); return

    def delete(self, key):
        node = self.find(key)
        if not node: return
        # After splay — node is at the root
        left, right = self.root.left, self.root.right
        if left:  left.parent  = None
        if right: right.parent = None
        if not left:
            self.root = right
        else:
            # find maximum in the left subtree → becomes new root
            self.root = left
            m = left
            while m.right: m = m.right
            self.splay(m)                  # m → root of the left part
            self.root.right = right
            if right: right.parent = self.root

Working Set Theorem

This is the primary theoretical strength of Splay Trees:

If element x was last requested t operations ago, the next access to x will take O(log t)

In practice: frequently used elements live close to the root and are found faster — the structure automatically adapts to real access patterns.

When to Choose What?

Scenario Recommendation
Cache with a hot subset ✅ Splay Tree
Database, on-disk indexes ✅ B+Tree
File system ✅ B-Tree / B+Tree
In-memory with uniform access ✅ Red-Black Tree / AVL
Need worst-case guarantees ✅ AVL / RB / B-Tree
Dynamic trees (Link-Cut) ✅ Splay Tree
Multithreaded (many readers) ❌ Splay is inconvenient (write on read)

💡 Core Intuition: A Splay Tree is like a stack of papers on a desk: the ones you work with most often end up on top. No external organization — the structure adapts to your work on its own.