Data Structure

Splay Tree

“The People Pleaser”

Search: O(log n) Amortized

Space: O(n)

Self-Balancing: Yes

History

Invented by Daniel Sleator and Robert Tarjan in 1985. They realized that in the real world, access patterns aren't random. If you ask for a data record once, you're likely to ask for it again very soon (the "locality of reference" principle).

The Splay Tree is designed to be lazy but accommodating. It adjusts itself based on *usage*, not just structure.

Core Property

Move-to-Root Heuristic

Whenever you access a node (search, insert, or update), that node is physically rotated all the way to the top of the tree to become the new root. Ideally, frequently accessed nodes stay near the top.

How It Works

The Splay Tree doesn't enforce height balance. Instead, it uses complex rotations to bring the target node to the root.

The Rotations (Splaying)

Zig: Single rotation (like AVL).
Zig-Zig: Two rotations in the same direction.
Zig-Zag: Two rotations in opposite directions.

By applying these repeatedly, the accessed node surfs to the top, and the tree roughly halves its depth along the access path.

SearchO(log n) Amortized

Individual operations can be slow ($O(n)$), but over a long sequence of operations, the average is logarithmic.

InsertO(log n) Amortized

We insert like a BST, then splay the new node to the root.

DeleteO(log n) Amortized

Splay the node to be deleted, then join the two resulting subtrees.

SpaceO(n)

Standard pointer-based tree storage.

Code Walkthrough

Complete data structure implementations in multiple programming languages. Select a language to view idiomatic code.

1class SplayNode:
2    """Node for Splay Tree."""
3    def __init__(self, val: int):
4        self.val = val
5        self.left: SplayNode | None = None
6        self.right: SplayNode | None = None
7
8
9class SplayTree:
10    """Self-adjusting Splay Tree using move-to-root heuristic."""
11    def __init__(self):
12        self.root: SplayNode | None = None
13
14    def _rotate_right(self, node: SplayNode) -> SplayNode:
15        """Zig rotation (right)."""
16        left = node.left
17        node.left = left.right
18        left.right = node
19        return left
20
21    def _rotate_left(self, node: SplayNode) -> SplayNode:
22        """Zag rotation (left)."""
23        right = node.right
24        node.right = right.left
25        right.left = node
26        return right
27
28    def _splay(self, node: SplayNode | None, val: int) -> SplayNode | None:
29        """Splay the node with given value to the root."""
30        if not node or node.val == val:
31            return node
32
33        # Value is in left subtree
34        if val < node.val:
35            if not node.left:
36                return node
37
38            # Zig-Zig (left-left)
39            if val < node.left.val:
40                node.left.left = self._splay(node.left.left, val)
41                node = self._rotate_right(node)
42
43            # Zig-Zag (left-right)
44            elif val > node.left.val:
45                node.left.right = self._splay(node.left.right, val)
46                if node.left.right:
47                    node.left = self._rotate_left(node.left)
48
49            return self._rotate_right(node) if node.left else node
50
51        # Value is in right subtree
52        else:
53            if not node.right:
54                return node
55
56            # Zag-Zag (right-right)
57            if val > node.right.val:
58                node.right.right = self._splay(node.right.right, val)
59                node = self._rotate_left(node)
60
61            # Zag-Zig (right-left)
62            elif val < node.right.val:
63                node.right.left = self._splay(node.right.left, val)
64                if node.right.left:
65                    node.right = self._rotate_right(node.right)
66
67            return self._rotate_left(node) if node.right else node
68
69    def insert(self, val: int) -> None:
70        """Insert value and splay it to root."""
71        if not self.root:
72            self.root = SplayNode(val)
73            return
74
75        self.root = self._splay(self.root, val)
76
77        if self.root.val == val:
78            return  # Value already exists
79
80        new_node = SplayNode(val)
81        if val < self.root.val:
82            new_node.right = self.root
83            new_node.left = self.root.left
84            self.root.left = None
85        else:
86            new_node.left = self.root
87            new_node.right = self.root.right
88            self.root.right = None
89
90        self.root = new_node
91
92    def search(self, val: int) -> SplayNode | None:
93        """Search for value, splaying accessed node to root."""
94        self.root = self._splay(self.root, val)
95        return self.root if self.root and self.root.val == val else None
96
97    def delete(self, val: int) -> None:
98        """Delete value from tree."""
99        if not self.root:
100            return
101
102        self.root = self._splay(self.root, val)
103
104        if self.root.val != val:
105            return  # Value not found
106
107        if not self.root.left:
108            self.root = self.root.right
109        else:
110            right = self.root.right
111            self.root = self._splay(self.root.left, val)
112            self.root.right = right

Python • .py

Real World Use Cases

1Implementing Caches (LRU-like behavior)
2Network routers (frequent IP lookups)
3Text editors (cursor operations)
4Garbage collection algorithms
5Data compression (Huffman coding variants)

Key Insights

It optimizes for 'Locality of Reference'.
Recently accessed elements are $O(1)$ to find again.
It does not store any balance metadata (lighter on memory than AVL).
It self-corrects: accessing a deep node fixes the tree along the path.

When to Use

Use Splay Trees when your access pattern is non-uniform (some items are popular, others are rare) or when implementing caching logic.

When NOT to Use

Avoid in real-time systems. Because a single search can trigger a massive tree reorganization ( $O(n)$ worst case), latency is unpredictable.

Watch Out

The Linear Worst Case. If you access elements in strict increasing order, a Splay Tree can momentarily turn into a stick before fixing itself. It offers 'amortized' guarantees, not strict ones.

Related Algorithms

Binary Search Tree

simpler version without splaying

O(h)

AVL Tree

strict balance alternative

O(log n)

Pathfinding

Breadth-First Search

level-order traversal

O(V + E)

Watch Splay Tree in Action