A splay tree is a binary search tree that rotates the last accessed node to its root. It stores no height or color balance metadata. A search follows ordinary key comparisons; on a hit it splays the found node, and on a miss this implementation splays the last node visited. The three rotation cases are a single step when the parent is the root, two aligned steps when node and parent sit on the same side, and two crossed steps otherwise. Each rotation keeps the in-order key sequence unchanged and repairs the moved subtree's parent pointer. The root can change even when a search returns false. That is a useful locality rule, but callers must not assume read-only lookups leave the tree shape unchanged.
Make this comfortable
Splay Trees: Access Rotations and Join Invariants
Operational case
A case index receives IDs 47, 19, 83, and 61. Its sorted output is 19, 47, 61, 83 regardless of the current root. Looking up 19 moves that case to the root. Searching for absent ID 55 visits the comparison path and then moves the last visited ID, 61, to the root; the operation still reports false. Removing 47 first splays it, detaches its two subtrees, splays the maximum of the left subtree, and attaches the right subtree there. The maximum-left node has no right child, so the join cannot violate key order. Both detached roots lose their former parent link before the join. A duplicate insertion is rejected, and its search may still reshape the tree.
Working Python program
class CaseNode:
def __init__(self, case_id):
self.case_id = case_id
self.left = None
self.right = None
self.parent = None
class SplayCaseIndex:
def __init__(self):
self.root = None
def _rotate(self, child):
parent = child.parent
grandparent = parent.parent
if child is parent.left:
parent.left = child.right
if child.right is not None:
child.right.parent = parent
child.right = parent
else:
parent.right = child.left
if child.left is not None:
child.left.parent = parent
child.left = parent
parent.parent = child
child.parent = grandparent
if grandparent is None:
self.root = child
elif parent is grandparent.left:
grandparent.left = child
else:
grandparent.right = child
def _splay(self, node):
while node.parent is not None:
parent = node.parent
grandparent = parent.parent
if grandparent is None:
self._rotate(node)
elif (node is parent.left) == (parent is grandparent.left):
self._rotate(parent)
self._rotate(node)
else:
self._rotate(node)
self._rotate(node)
def find(self, case_id):
current = self.root
last = None
while current is not None:
last = current
if case_id == current.case_id:
self._splay(current)
return True
current = current.left if case_id < current.case_id else current.right
if last is not None:
self._splay(last)
return False
def insert(self, case_id):
if self.root is None:
self.root = CaseNode(case_id)
return True
if self.find(case_id):
return False
old_root = self.root
fresh = CaseNode(case_id)
if case_id < old_root.case_id:
fresh.left = old_root.left
if fresh.left is not None:
fresh.left.parent = fresh
fresh.right = old_root
old_root.left = None
else:
fresh.right = old_root.right
if fresh.right is not None:
fresh.right.parent = fresh
fresh.left = old_root
old_root.right = None
old_root.parent = fresh
self.root = fresh
return True
def remove(self, case_id):
if not self.find(case_id):
return False
old_root = self.root
left, right = old_root.left, old_root.right
if left is not None:
left.parent = None
if right is not None:
right.parent = None
old_root.left = old_root.right = None
if left is None:
self.root = right
return True
self.root = left
maximum = left
while maximum.right is not None:
maximum = maximum.right
self._splay(maximum)
self.root.right = right
if right is not None:
right.parent = self.root
return True
def ordered_ids(self):
result = []
stack = []
current = self.root
while stack or current is not None:
while current is not None:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.case_id)
current = current.right
return result
cases = SplayCaseIndex()
for case_id in (47, 19, 83, 61):
cases.insert(case_id)
print(cases.ordered_ids())
print(cases.find(19), cases.root.case_id)
print(cases.find(55), cases.root.case_id)
print(cases.remove(47), cases.ordered_ids())Output
[19, 47, 61, 83]
True 19
False 61
True [19, 61, 83]Time, space, and tradeoff
A single lookup, insertion, or removal can traverse a chain of n nodes and cost O(n). Over a sequence of standard operations, the splay-tree access bound is O(log n) amortized per operation. The word amortized matters: it gives no per-request tail-latency cap. Node storage is O(n); the iterative search, rotations, and in-order walk avoid recursion, while the output list and traversal stack use O(n) extra space in the worst case. A stable-height AVL or red-black tree is preferable when the application needs a bound for every individual lookup. This model uses integer IDs, one process, and no concurrent readers; a concurrent search would mutate shared links and need synchronization. It also makes no claim about CPU-cache speed.
Common Mistakes
- Do not call the current tree height logarithmic after every operation.
- Do not forget the moved middle subtree's parent pointer during a rotation.
- Do not treat an unsuccessful lookup as shape-preserving in this implementation.
- Do not attach the right subtree before exposing the maximum of the left subtree during removal.
Connected lessons
- Trees and Heaps
- Data Structures
- Binary search trees: preserve order through every branch
- AVL trees: restore height balance after insertion
- Skip lists: randomized levels over an ordered bottom chain
- Projects
- Quizzes
Compare the operation contract with Resident LRU-K: Evict by the Kth Recent Reference, then work through the audit project and contract quiz.
Scapegoat trees: rebuild a deep insertion subtree adds a distinct structure contract to compare.
data structures
trees-and-heaps