Splay Tree — Полное руководство

Что такое Splay Tree?

Splay Tree (расширяющееся дерево) — это самобалансирующееся бинарное дерево поиска, разработанное Даниэлем Слейтором и Робертом Тарьяном в 1985 году.

Ключевая идея: каждый раз при обращении к узлу он перемещается в корень дерева с помощью операции splay (серии поворотов). Нет хранения высоты, цвета, или других метаданных — только указатели parent/left/right.

Структура узла

class SplayNode:
    def __init__(self, key, value=None):
        self.key    = key
        self.value  = value
        self.left   = None   # левое поддерево  (ключи < key)
        self.right  = None   # правое поддерево (ключи > key)
        self.parent = None   # родитель

Основная операция — Splay (расширение)

Splay перемещает узел x в корень через три случая поворотов:

flowchart TD A[Узел X нужно поднять в корень] --> B{X — уже корень?} B -- Да --> Z[Готово] B -- Нет --> C{Родитель P — корень?} C -- Да --> D["Zig: один поворот\n(Left или Right)"] D --> Z C -- Нет --> E{X и P — одна сторона?} E -- Да --> F["Zig-Zig: два одинаковых поворота\n(оба Left или оба Right)"] E -- Нет --> G["Zig-Zag: два разных поворота\n(Left+Right или Right+Left)"] F --> A G --> A

Три случая поворотов

flowchart LR subgraph ZIG["🔄 ZIG — P является корнем"] direction TB z1["G — P — X"] -->|"Right Rotate(P)"| z2["X → P → G"] end subgraph ZIGZIG["🔄🔄 ZIG-ZIG — X и P на одной стороне"] direction TB zz1["G → P → X"] -->|"Rotate(G) then Rotate(P)"| zz2["X → P → G"] end subgraph ZIGZAG["↩️↪️ ZIG-ZAG — X и P на разных сторонах"] direction TB zzg1["G → P ↘ X"] -->|"Rotate(P) then Rotate(G)"| zzg2["P ← X → G"] end

Пошаговый пример — Insert + Splay

Вставляем ключи: 10, 20, 5, 15, 30 и затем делаем find(5)

После вставки всех ключей (без балансировки):

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

После find(5) — узел 5 поднимается в корень:

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

Примеры применения

mindmap root((Splay Tree)) Кэширование LRU-подобные кэши DNS кэш CPU instruction cache Сети IP маршрутизация Firewall rule lookup Компиляторы Symbol tables Scope management Базы данных Windows NT registry Буферный пул Алгоритмы Link-Cut Trees Dynamic trees Top trees

Конкретные кейсы

Применение Почему Splay Tree?
Кэш браузера Недавно открытые URL снова нужны быстро → они в корне
Текстовый редактор Последние правки локальны → cursor position быстро находится
Сетевой маршрутизатор «Горячие» IP-адреса постоянно в топе
Windows NT Registry Часто читаемые ключи всплывают наверх
Garbage Collector (JVM) Поиск свободных блоков по размеру
Link-Cut Trees Splay — строительный блок для динамических деревьев

Таблица сложности

Операция 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-й элемент O(n) O(log n) O(1)

⚠️ Worst case O(n) — одна операция, но серия из m операций всегда ≤ O(m log n)

Ключевые Плюсы и Минусы

✅ Преимущества ❌ Недостатки
Простая реализация Worst-case O(n)
Адаптация к паттерну доступа Не для real-time
Отличная cache locality Плохо при равномерном доступе
Split/Merge O(log n) Не persistent
Хорош для skewed access find меняет дерево

Splay Tree vs B-Tree vs B+Tree

Характеристика Splay Tree B-Tree B+Tree
Структура Бинарное M-арное M-арное
Хранение данных Все узлы Все узлы Только листья
Оптимизация RAM / Cache Диск Диск + Range
Балансировка Амортизированная Строгая Строгая
Высота дерева O(log n) amotr. O(log_m n) O(log_m n)
Locality of reference ✅ Отличная ❌ Нет ❌ Нет
Range queries ⚠️ Средне ⚠️ Средне ✅ Отлично
Sequential scan ❌ Плохо ⚠️ Средне ✅ Отлично
Overhead памяти ✅ Минимальный ⚠️ Средний ⚠️ Средний
Метаданные узла ❌ Нет Degree/count Degree/count
Worst-case 1 op ❌ O(n) ✅ O(log n) ✅ O(log n)
Применение Cache, RAM FS, DB Index СУБД, OS

Производительность при разных паттернах доступа

{
  "title": { "text": "Относительная производительность по паттерну доступа", "left": "center" },
  "tooltip": { "trigger": "axis", "axisPointer": { "type": "shadow" } },
  "legend": { "top": 30, "data": ["Splay Tree", "B-Tree", "B+Tree"] },
  "xAxis": {
    "type": "category",
    "data": ["Случайный", "Локальный (80/20)", "Последовательный", "Range Scan", "Вставка потоком"]
  },
  "yAxis": {
    "type": "value",
    "name": "Score (выше = лучше)",
    "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" }
    }
  ]
}

Реализация — ключевые операции (Python)

class SplayTree:

    def _right_rotate(self, x):
        p = x.parent
        b = x.right
        # x поднимается, p опускается вправо
        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:                        # пока x не корень
            p = x.parent
            g = p.parent                       # дедушка
            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 (левый-левый)
                self._right_rotate(p)
                self._right_rotate(x)
            elif g.right == p and p.right == x:
                # Zig-Zig (правый-правый)
                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)           # найден → в корень
                return node
            elif key < node.key: node = node.left
            else:                node = node.right
        if last: self.splay(last)          # не найден → splay последнего
        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         # обновить
                self.splay(node); return

    def delete(self, key):
        node = self.find(key)
        if not node: return
        # После splay — node в корне
        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:
            # найти максимум в левом поддереве → станет новым корнем
            self.root = left
            m = left
            while m.right: m = m.right
            self.splay(m)                  # m → корень левого
            self.root.right = right
            if right: right.parent = self.root

Теорема о рабочем множестве (Working Set Theorem)

Это главная теоретическая сила Splay Tree:

Если элемент x был запрошен t операций назад, то следующий доступ к x займёт O(log t)

Практически: часто используемые элементы живут близко к корню и находятся быстрее — структура адаптируется к реальному паттерну доступа автоматически.

Когда выбирать что?

Сценарий Рекомендация
Кэш с горячим подмножеством ✅ Splay Tree
База данных, индексы на диске ✅ B+Tree
Файловая система ✅ B-Tree / B+Tree
In-memory с равномерным доступом ✅ Red-Black Tree / AVL
Нужны гарантии worst-case ✅ AVL / RB / B-Tree
Динамические деревья (Link-Cut) ✅ Splay Tree
Multithreaded (много читателей) ❌ Splay неудобен (write on read)

💡 Главная интуиция: Splay Tree — это как стопка документов на столе: те, с которыми работаешь чаще, оказываются сверху. Никакой внешней организации — структура сама приспосабливается к вашей работе.