Implementing A Splay Tree For Self-Optimizing Search

A splay tree is a binary search tree that moves recently accessed nodes towards the root. It does this through rotations rather than maintaining an explicit height or balance field. The result is a data structure that adapts to the order of operations: keys requested repeatedly become cheap to find, while rarely used keys gradually move deeper.

This behaviour makes splay trees useful when access patterns are uneven, such as symbol tables, caches, editor buffers, and interactive indexes. For an Australian application, a transport lookup might repeatedly access busy Sydney stations during peak time, while a rural stop is queried only occasionally. A self-adjusting tree can respond to that workload without being told which records are “hot”.

Why Splay Trees Adapt

A conventional binary search tree places a key according to its value. If keys arrive in sorted order, however, the tree can become a chain with linear search time. AVL and red-black trees prevent that shape by enforcing balance rules. A splay tree takes a different approach: it accepts that one operation can be expensive and improves the structure around the keys that are being used.

After searching for a key, the tree splays the found node to the root. If the key is absent, the last node visited is usually splayed instead. This still helps because future searches near the failed key can start from a more relevant location. Insertions and deletions also use splaying to place the affected region at the root before changing links.

The main performance guarantee is amortised O(log n) time over a sequence of m operations, where n is the number of stored keys. A single operation can cost O(n), especially when the tree is initially skewed. That trade-off suits workloads with locality of reference: recently used or nearby keys tend to be requested again. For a broader comparison of algorithmic cost, the discussion of negative-weight paths is a useful reminder that worst-case and aggregate guarantees describe different aspects of an algorithm.

Rotations And Core Invariants

Splaying uses three rotation patterns. A zig step rotates a child above its parent when the child is the root’s direct child. A zig-zig step performs two rotations in the same direction, such as right-right when a node and its parent are both left children. A zig-zag step performs rotations in opposite directions, such as left-right.

These operations preserve the binary-search-tree invariant. Every key in a node’s left subtree remains smaller, and every key in its right subtree remains larger. The rotations change only the shape, not the in-order sequence of keys. That is the central correctness property to protect during implementation.

A practical implementation needs either parent pointers or a top-down splaying algorithm. Parent pointers make the cases easy to follow and are suitable for educational code. Each node stores key, value, left, right, and parent. During a rotation, all affected child and parent references must be updated, including the tree’s root when the rotated node reaches the top.

A Python Implementation

The following implementation uses parent pointers. _rotate_left and _rotate_right handle local structural changes, while _splay repeatedly moves a node upward. The comparisons are based on keys, so values can hold any associated record.

class Node:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        self.parent = None


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

    def _replace_parent_link(self, old, new):
        if old.parent is None:
            self.root = new
        elif old is old.parent.left:
            old.parent.left = new
        else:
            old.parent.right = new
        if new:
            new.parent = old.parent

    def _rotate_left(self, x):
        y = x.right
        if y is None:
            return
        x.right = y.left
        if y.left:
            y.left.parent = x
        self._replace_parent_link(x, y)
        y.left = x
        x.parent = y

    def _rotate_right(self, x):
        y = x.left
        if y is None:
            return
        x.left = y.right
        if y.right:
            y.right.parent = x
        self._replace_parent_link(x, y)
        y.right = x
        x.parent = y

    def _splay(self, x):
        while x.parent:
            p = x.parent
            g = p.parent

            if g is None:  # zig
                if x is p.left:
                    self._rotate_right(p)
                else:
                    self._rotate_left(p)
            elif x is p.left and p is g.left:  # zig-zig
                self._rotate_right(g)
                self._rotate_right(p)
            elif x is p.right and p is g.right:
                self._rotate_left(g)
                self._rotate_left(p)
            elif x is p.right:  # zig-zag
                self._rotate_left(p)
                self._rotate_right(g)
            else:
                self._rotate_right(p)
                self._rotate_left(g)
        return x

    def search(self, key):
        node = self.root
        last = None

        while node:
            last = node
            if key == node.key:
                return self._splay(node).value
            node = node.left if key < node.key else node.right

        if last:
            self._splay(last)
        return None

The search method splays a successful match and also splays the final node after a miss. Returning None for a missing key is convenient for a tutorial, although production code may use a sentinel so that stored None values remain distinguishable. An insert operation can search for the key, update an existing value, or attach a new node below the current root before splaying it. Deletion generally splays the target to the root, separates its left and right subtrees, splays the largest node in the left subtree, and attaches the right subtree.

Complexity And Workload Behaviour

The amortised bound comes from a potential-based analysis of the tree’s shape. Splaying repeatedly shortens expensive paths and brings frequently accessed nodes near the root. A sequence containing repeated searches for the same key becomes very fast after the first access. Sequential scans can also perform well because each access changes the shape in a useful direction.

Space usage is O(n), with one node per key and a parent pointer in each node. Search, insertion, and deletion are O(log n) amortised, but O(n) in the worst case for an individual operation. Unlike an AVL tree, a splay tree does not offer a strict logarithmic bound for every request. That matters in latency-sensitive services where one slow lookup is unacceptable.

Splay trees also have no stored balance factor or colour bit, so their metadata is simple. They can be a strong choice for an in-memory dictionary with a changing hot set, a compiler’s recently used symbols, or a text editor’s cursor neighbourhood. They are less attractive for read-heavy concurrent systems: rotations mutate the tree during a search, and coarse locking can make contention costly.

Key comparison must be consistent. If strings are compared using case folding, every operation must use the same rule. If records use composite keys, define their ordering clearly rather than relying on accidental Python object behaviour. For text-oriented data, ideas from a text classification guide also highlight why normalisation decisions should be explicit before values enter an index.

Testing And Practical Recommendations

Tests should check both returned values and tree structure. Insert keys in sorted, reverse-sorted, and random order, then verify an in-order traversal is sorted. Search for present and absent keys, confirming that a successful key reaches the root and that a failed search splays the last visited node. Repeatedly insert and delete the same key to expose stale parent pointers.

A useful invariant checker can walk every node and assert that its parent points back to the node. It can also carry lower and upper key bounds through recursion, ensuring that no rotation has placed a key on the wrong side. For performance tests, record operation sequences rather than timing one isolated lookup; amortised structures need representative workloads.

For an Australian team, benchmark with realistic access traces rather than assuming a generic database pattern. A Brisbane service with a few heavily used suburbs, a Melbourne timetable tool during the morning peak, or a Perth inventory system with seasonal demand may all produce different locality. The everyday term “arvo” may appear in test data or logs, but the ordering rule should remain technical and deterministic.

• Use a splay tree when recent-access locality is strong and occasional slow operations are acceptable.
• Choose an AVL or red-black tree when predictable per-operation latency matters more than adaptive behaviour.
• Keep parent-pointer updates in small rotation methods and test each rotation independently.
• Splay the last visited node after a failed lookup when nearby future searches are likely.
• Measure complete operation traces, including misses, inserts, deletes, and repeated hot-key accesses.
• Use a sentinel or explicit result type if stored values may legitimately be None.

A correct implementation is defined by both ordering and adaptation. Once rotations preserve the search-tree invariant and tests verify parent links, the splay policy can improve naturally as the workload changes. The structure earns its value from that feedback loop: access changes shape, and shape changes the cost of later access.