icaoberg / Data structures - Splay Tree

Created Sun, 03 May 2026 00:00:00 +0000 Modified Sun, 03 May 2026 09:38:20 -0400

Jupyter Notebook python

Data structures - Splay Tree¶

A splay tree is a self-adjusting binary search tree. Every access (search, insert, or delete) performs a splay operation that moves the accessed node to the root via a series of tree rotations. Recently accessed nodes stay near the root, giving excellent amortized O(log n) performance and strong cache locality for workloads with temporal locality.

This notebook covers:

What is a Splay Tree?
The SplayTree class
Core operations: insert, search, delete, inorder
Example: LRU-style word frequency counter

1. What is a Splay Tree?¶

A splay tree is a BST where every operation ends by splaying the target node to the root using three rotation cases:

Case	Condition	Action
Zig	Parent is root	Single rotation
Zig-Zig	Node and parent are both left (or both right) children	Rotate parent first, then node
Zig-Zag	Node is left child, parent is right child (or vice-versa)	Rotate node twice

   Zig (right rotation at P)       Zig-Zig (right-right)        Zig-Zag (left then right)

       P            X                  G            X              G            X
      / \          / \                / \          / \            / \          / \
     X   C  -->  A   P              P   D  -->  A   P          P   D  -->  X   G
    / \              / \           / \              / \        / \          |   |
   A   B            B   C         X   C            B   G      A   X        A   D
                                 / \                  / \        / \
                                A   B                B   C      B   C

Key properties:

No balance metadata (no height, color, or rank stored per node)
Amortized O(log n) per operation
O(log n) amortized for any sequence of m operations on an n-node tree: O((m+n) log n)
Self-optimizing: frequently accessed keys migrate toward the root

2. The `SplayTree` class¶

In [1]:

class Node:
    __slots__ = ('key', 'value', 'left', 'right', 'parent')

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


class SplayTree:
    """Self-adjusting binary search tree (Sleator & Tarjan, 1985)."""

    def __init__(self):
        self.root = None
        self._size = 0

    # ------------------------------------------------------------------
    # Internal rotation helpers
    # ------------------------------------------------------------------

    def _set_parent(self, node, parent):
        if node is not None:
            node.parent = parent

    def _rotate_right(self, x):
        """Right-rotate around x: x's left child becomes the new subtree root."""
        y = x.left
        x.left = y.right
        self._set_parent(y.right, x)
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x is x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.right = x
        x.parent = y

    def _rotate_left(self, x):
        """Left-rotate around x: x's right child becomes the new subtree root."""
        y = x.right
        x.right = y.left
        self._set_parent(y.left, x)
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x is x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    # ------------------------------------------------------------------
    # Splay
    # ------------------------------------------------------------------

    def _splay(self, x):
        """Move node x to the root using zig / zig-zig / zig-zag steps."""
        while x.parent is not None:
            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 (left-left)
                self._rotate_right(g)
                self._rotate_right(p)
            elif x is p.right and p is g.right:
                # Zig-Zig (right-right)
                self._rotate_left(g)
                self._rotate_left(p)
            elif x is p.right and p is g.left:
                # Zig-Zag (left-right)
                self._rotate_left(p)
                self._rotate_right(g)
            else:
                # Zig-Zag (right-left)
                self._rotate_right(p)
                self._rotate_left(g)

    # ------------------------------------------------------------------
    # Public API
    # ------------------------------------------------------------------

    def insert(self, key, value=None):
        """Insert key (with optional value). Replaces value if key exists."""
        if self.root is None:
            self.root = Node(key, value)
            self._size += 1
            return
        current = self.root
        while True:
            if key < current.key:
                if current.left is None:
                    node = Node(key, value)
                    node.parent = current
                    current.left = node
                    self._splay(node)
                    self._size += 1
                    return
                current = current.left
            elif key > current.key:
                if current.right is None:
                    node = Node(key, value)
                    node.parent = current
                    current.right = node
                    self._splay(node)
                    self._size += 1
                    return
                current = current.right
            else:
                # Key already present — update value and splay
                current.value = value
                self._splay(current)
                return

    def search(self, key):
        """Return value for key, or None. Splays the accessed node."""
        current = self.root
        last = None
        while current:
            last = current
            if key < current.key:
                current = current.left
            elif key > current.key:
                current = current.right
            else:
                self._splay(current)
                return current.value
        # Key not found — splay the last visited node to amortize cost
        if last:
            self._splay(last)
        return None

    def delete(self, key):
        """Remove key from the tree. Raises KeyError if not found."""
        current = self.root
        while current:
            if key < current.key:
                current = current.left
            elif key > current.key:
                current = current.right
            else:
                self._splay(current)
                # Split into left and right subtrees
                left = self.root.left
                right = self.root.right
                if left:
                    left.parent = None
                if right:
                    right.parent = None
                if left is None:
                    self.root = right
                elif right is None:
                    self.root = left
                else:
                    # Splay the maximum of the left subtree, then attach right
                    self.root = left
                    cur = left
                    while cur.right:
                        cur = cur.right
                    self._splay(cur)
                    self.root.right = right
                    right.parent = self.root
                self._size -= 1
                return
        raise KeyError(key)

    def inorder(self):
        """Return all (key, value) pairs in sorted key order."""
        result = []
        def _walk(node):
            if node:
                _walk(node.left)
                result.append((node.key, node.value))
                _walk(node.right)
        _walk(self.root)
        return result

    def __contains__(self, key):
        return self.search(key) is not None

    def __len__(self):
        return self._size

    def __repr__(self):
        root_key = self.root.key if self.root else None
        return f"SplayTree(size={self._size}, root={root_key!r})"

3. Core operations¶

In [2]:

st = SplayTree()
for k in [10, 5, 15, 3, 7, 12, 20]:
    st.insert(k)
    print(f"insert({k:2d})  root={st.root.key:2d}  tree={st}")

print()
print("Inorder:", [k for k, _ in st.inorder()])

insert(10)  root=10  tree=SplayTree(size=1, root=10)
insert( 5)  root= 5  tree=SplayTree(size=2, root=5)
insert(15)  root=15  tree=SplayTree(size=3, root=15)
insert( 3)  root= 3  tree=SplayTree(size=4, root=3)
insert( 7)  root= 7  tree=SplayTree(size=5, root=7)
insert(12)  root=12  tree=SplayTree(size=6, root=12)
insert(20)  root=20  tree=SplayTree(size=7, root=20)

Inorder: [3, 5, 7, 10, 12, 15, 20]

In [3]:

print("search(7):  ", st.search(7),  " → root now:", st.root.key)
print("search(15): ", st.search(15), " → root now:", st.root.key)
print("search(99): ", st.search(99), " → root now:", st.root.key)  # not found

search(7):   None  → root now: 7
search(15):  None  → root now: 15
search(99):  None  → root now: 20

In [4]:

print("Before delete:", [k for k, _ in st.inorder()])
st.delete(5)
print("After delete(5):", [k for k, _ in st.inorder()], " root:", st.root.key)
st.delete(10)
print("After delete(10):", [k for k, _ in st.inorder()], " root:", st.root.key)

Before delete: [3, 5, 7, 10, 12, 15, 20]
After delete(5): [3, 7, 10, 12, 15, 20]  root: 3
After delete(10): [3, 7, 12, 15, 20]  root: 7

In [5]:

try:
    st.delete(999)
except KeyError as e:
    print("KeyError:", e)

print("Contains 7:", 7 in st)
print("Contains 5:", 5 in st)

KeyError: 999
Contains 7: False
Contains 5: False

4. Example: LRU-style word frequency counter¶

Splay trees are well-suited for frequency counting in text: the most recently (and frequently) accessed words naturally migrate to the root, acting like a soft cache. We insert each word with a count of 1, and increment on repeated encounters.

In [6]:

class WordFrequencyCounter:
    """Count word frequencies using a SplayTree as the backing store."""

    def __init__(self):
        self._tree = SplayTree()

    def add(self, word):
        word = word.lower()
        count = self._tree.search(word)
        self._tree.insert(word, (count or 0) + 1)

    def count(self, word):
        return self._tree.search(word.lower()) or 0

    def top_n(self, n=10):
        """Return the n most frequent words as (word, count) pairs."""
        all_items = self._tree.inorder()
        return sorted(all_items, key=lambda x: -x[1])[:n]

    def __len__(self):
        return len(self._tree)

    @property
    def hot_word(self):
        """The word at the splay-tree root — the most recently accessed."""
        return self._tree.root.key if self._tree.root else None

In [7]:

text = """
To be or not to be that is the question
Whether tis nobler in the mind to suffer
The slings and arrows of outrageous fortune
Or to take arms against a sea of troubles
And by opposing end them to die to sleep
No more and by a sleep to say we end
The heartache and the thousand natural shocks
That flesh is heir to tis a consummation
Devoutly to be wished to die to sleep
To sleep perchance to dream
"""

import re
counter = WordFrequencyCounter()
for word in re.findall(r"[a-zA-Z']+", text):
    counter.add(word)

print(f"Unique words: {len(counter)}")
print(f"Hot word (last accessed): {counter.hot_word!r}")
print()
print("Top 10 most frequent words:")
for word, cnt in counter.top_n(10):
    bar = '█' * cnt
    print(f"  {word:<15} {cnt:3d}  {bar}")

Unique words: 47
Hot word (last accessed): 'dream'

Top 10 most frequent words:
  to               13  █████████████
  the               5  █████
  and               4  ████
  sleep             4  ████
  a                 3  ███
  be                3  ███
  by                2  ██
  die               2  ██
  end               2  ██
  is                2  ██

In [8]:

# Demonstrate the splay property: repeated access pulls a word to the root
print("Root before repeated access:", counter.hot_word)
for _ in range(5):
    counter.count("sleep")
print("Root after 5x accessing 'sleep':", counter.hot_word)

counter.count("dream")
print("Root after accessing 'dream':", counter.hot_word)

Root before repeated access: dream
Root after 5x accessing 'sleep': sleep
Root after accessing 'dream': dream

Licensed under the GNU General Public License v2.0 (GPL-2).
You may redistribute and/or modify this work under the terms of GPL-2.
This work is distributed WITHOUT ANY WARRANTY.
Happy computing.