Splay-дерево: самобалансирующееся BST через продвижение к корню

Splay-дерево - самобалансирующееся двоичное дерево поиска, придуманное Дэниелом Слейтором и Робертом Тарьяном в 1985 году. В отличие от AVL и красно-чёрных деревьев, оно не хранит ни высот, ни цветов и вообще не пытается удерживать строгий баланс. Вся идея сводится к одному правилу: каждый раз, когда мы обращаемся к узлу, мы продвигаем его в корень через цепочку поворотов - эта операция называется splay. Удивительно, но такого «ленивого» правила достаточно, чтобы любая последовательность $m$ операций над деревом из $n$ узлов укладывалась в $O((m + n) \log n)$ времени. То есть в среднем по последовательности - $O(\log n)$ на операцию.

Базовая идея - почему продвигать к корню

Классическая операция в BST - поиск ключа $x$ - естественно проходит по цепочке от корня к найденному узлу. Splay-дерево превращает этот же путь в инструмент перестройки: после поиска узел $x$ становится новым корнем, а все вершины, через которые мы прошли, перебалансируются так, чтобы их глубина уменьшилась примерно вдвое.

Эффект - «само-настройка» под паттерн доступа. Если приложение часто запрашивает один и тот же ключ, он живёт около корня и достаётся за $O(1)$. Если паттерн - LRU-подобный (горячие узлы быстро мигрируют наверх), splay-дерево автоматически их кэширует. Это похоже на самонастраивающийся хэш с порядком, который ещё и поддерживает range queries.

Три случая поворотов: zig, zig-zig, zig-zag

Splay узла $x$ - это последовательность шагов, на каждом из которых $x$ поднимается на 1 или 2 уровня. Чтобы выбрать конкретный шаг, смотрим на $x$, его родителя $p$ и деда $g$.

Zig - одиночный поворот. Срабатывает, когда $p$ - корень (деда нет). Делаем один поворот вокруг ребра $(p, x)$, после которого $x$ становится корнем. Этот случай - последний в цепочке, к нему приходим, когда у $x$ остался только один уровень до корня.

$$\text{zig:} \quad p(x) \;\to\; \text{rotate}(p, x), \quad x \text{ становится корнем}$$

Zig-zig - двойной поворот в одну сторону. $x$ и $p$ - оба левые дети (или оба правые). Делаем два поворота в правильном порядке: сначала вокруг $(g, p)$, потом вокруг $(p, x)$. Именно такой порядок принципиально отличает splay от наивного «дважды поверни». Если поворачивать наоборот (сначала $x$, потом $p$), амортизированная оценка $O(\log n)$ ломается - глубина соседних узлов остаётся неизменной, и в худшем сценарии дерево превращается в список.

Zig-zag - двойной поворот в разные стороны. $x$ - левый ребёнок $p$, а $p$ - правый ребёнок $g$ (или симметрично). Делаем два поворота: сначала вокруг $(p, x)$, потом вокруг $(g, x)$. Это в точности тот же двойной поворот, что используется при балансировке AVL в случае «LR/RL».

Каждый шаг splay завершён либо в zig (когда дед отсутствует), либо в zig-zig/zig-zag (когда дед есть). После шага $x$ оказывается на 2 уровня выше (или на 1, если был zig). Повторяем, пока $x$ не дойдёт до корня.

Операции дерева через splay

Все операции сводятся к одной - собственно splay. Это и есть главная архитектурная находка Слейтора и Тарьяна.

• Поиск $x$. Идём по BST от корня вниз, как обычно. В конце вызываем $\text{splay}(x)$, если ключ нашли, или $\text{splay}(y)$ для последней посещённой вершины $y$ при отсутствии ключа.
• Вставка $x$. Стандартная BST-вставка, затем $\text{splay}(x)$ - новый узел сразу оказывается в корне.
• Удаление $x$. Сначала $\text{splay}(x)$ - узел поднялся в корень. Затем удаляем корень: его левое поддерево $L$ и правое поддерево $R$ независимы. Делаем $\text{splay}$ максимального элемента в $L$ - он становится новым корнем $L$ с пустым правым ребёнком; подвешиваем $R$ туда. Операция называется join.
• Split по ключу $x$. $\text{splay}(x)$, после чего разрезаем дерево по корню: левое поддерево с ключами $\le x$ и правое с ключами $> x$ - готовые два дерева.

Заметьте, что join и split - две элементарные операции, на которых внутри устроены все остальные. В AVL/Red-Black эквивалентные операции требуют отдельной нетривиальной логики; в splay они получаются почти бесплатно из основного механизма.

Амортизированный анализ: potential function

Пиковая стоимость одной операции в splay-дереве может быть $O(n)$ - например, если дерево вырождено в список и мы обращаемся к самой нижней вершине. Но по последовательности средняя стоимость всё равно $O(\log n)$. Доказывается через функцию потенциала (метод Тарьяна) - тот же приём, что даёт амортизированную оценку и для кучи Фибоначчи.

Определим $w(x) \ge 1$ - произвольный положительный вес узла, $s(x)$ - суммарный вес поддерева с корнем $x$, $r(x) = \log s(x)$ - ранг узла. Потенциал всего дерева:

$$\Phi = \sum_{x \in T} r(x) = \sum_{x \in T} \log s(x)$$

Лемма access: амортизированная стоимость операции $\text{splay}(x)$ ограничена

$$\hat{c}(x) \;\le\; 3 \bigl(r(\text{root}) - r(x)\bigr) + 1 \;=\; O(\log n)$$

если все веса равны $1$, то $r(\text{root}) = \log n$.

Доказательство опирается на оценку каждого из трёх случаев поворота. Для шага zig-zig ключевое неравенство:

$$r'(x) + r'(p) + r'(g) - r(x) - r(p) - r(g) \;\le\; 3(r'(x) - r(x)) - 2$$

где $r'$ - ранги после шага. Реальная стоимость шага равна $2$ (два поворота); за счёт уменьшения потенциала телескопическая сумма всех шагов splay сворачивается в $3(r(\text{root}) - r(x))$, что и даёт оценку. Случай zig-zag даёт ту же оценку с константой 2 вместо 3, zig - однократную «утечку» $3(r'(x) - r(x)) + 1$.

В сумме по $m$ операциям амортизированный счёт даёт $O(m \log n + n \log n)$ - второе слагаемое - это начальный потенциал, который мы платим один раз.

Сильные свойства: working-set, static optimality, dynamic finger

Из амортизационной леммы выводятся несколько глубоких теорем, для большинства из которых сами авторы доказали лишь часть, а сильные версии завершили позже.

• Static optimality. Сложность splay-дерева на любой последовательности доступов сравнима со сложностью наилучшего статического BST, оптимизированного под эту же последовательность. То есть splay автоматически делает то же, что делает заранее посчитанное оптимальное BST.
• Working-set theorem. Стоимость доступа к узлу $x$ - это $O(\log w(x))$, где $w(x)$ - размер «рабочего множества» (число различных ключей, запрошенных с прошлого обращения к $x$). Это формализация интуиции про LRU-кэш: чаще трогаешь - быстрее достаёшь.
• Dynamic finger. Если последовательные запросы близки по ключу - стоимость очередного запроса логарифмически зависит от расстояния, а не от $n$. Гипотеза доказана Коулом, Минцем и Сандэрсом в 2000 году.
• Гипотеза динамической оптимальности. Слейтор и Тарьян предположили, что splay-дерево с точностью до константы оптимально среди всех динамических BST - гипотеза до сих пор открыта.

Сравнение с AVL и красно-чёрным деревом

AVL и красно-чёрные деревья дают жёсткую гарантию $O(\log n)$ на каждую операцию - это важно для систем реального времени, где недопустимо разовое торможение. На дисковом уровне ту же задачу решают B-деревья - у них тоже жёсткий инвариант высоты, но за счёт ширины узла. Splay-дерево, наоборот, обещает только амортизацию: одна конкретная операция вполне может задеть $\Theta(n)$ узлов, если перед ней дерево было сильно перекошено.

Зато splay выигрывает на типичных load patterns. Если в последовательности обращений есть «горячая» подгруппа ключей (а почти любая реальная нагрузка такова), AVL/Red-Black хранят их где попало в дереве, а splay автоматически переносит наверх. Плюс отсутствие служебных полей у узла: для систем, где миллионы маленьких узлов и важна память, это ощутимая экономия.

Применения

• Memory allocators. Аллокатор dlmalloc использовал splay-дерево для управления свободными блоками - горячие блоки автоматически оказывались наверху.
• Сжатие данных. Алгоритм splay-tree compression Гранхэма и Витти - арифметическое кодирование с динамическим контекстом, в котором частые символы оказываются у корня.
• Link/cut trees. Структура Слейтора-Тарьяна для динамической связности на лесах деревьев строится поверх splay-деревьев - каждый «предпочтительный путь» хранится как splay-дерево.
• Виртуальная память. Некоторые ОС используют splay-деревья для управления VMA (virtual memory areas) - там типичны повторные обращения к одной и той же области.

Частые ошибки

• Перепутать порядок поворотов в zig-zig. Сначала поворот вокруг $(g, p)$, потом $(p, x)$ - не наоборот. С обратным порядком асимптотика разваливается, и дерево деградирует на патологических последовательностях.
• Забыть про splay в неудачном поиске. Если ключа нет, в корень всё равно нужно поднять последнюю посещённую вершину - иначе следующее обращение к близкому ключу не получит amortized-выгоды.
• Применять splay в multi-threaded коде без локов. Любая операция, включая read-only поиск, мутирует структуру - без блокировок splay-дерево нельзя разделять между потоками. AVL и Red-Black с этой точки зрения дружелюбнее.
• Ожидать $O(\log n)$ на каждую операцию. Splay даёт амортизированную оценку; конкретная операция может занять $O(n)$. В hard real-time системах это критично.
• Использовать splay для статических данных. Если данные не меняются и запросы равномерные, простое сбалансированное BST без splay будет быстрее: вы не платите за повороты.

FAQ

Чем splay-дерево принципиально отличается от AVL? AVL поддерживает строгое условие баланса (разность высот поддеревьев $\le 1$) и хранит высоту в каждом узле. Splay не поддерживает баланс вообще - он перестраивается реактивно после каждого обращения. AVL гарантирует $O(\log n)$ на любую конкретную операцию, splay только в среднем по последовательности.

Что доказывает «гипотеза динамической оптимальности»? Гипотеза утверждает, что splay-дерево с точностью до константы оптимально среди всех динамических BST на любой последовательности обращений. Static optimality (теорема, а не гипотеза) - слабее: оптимальность только относительно лучшего фиксированного дерева. Полная динамическая оптимальность до сих пор не доказана и не опровергнута - это одна из самых известных открытых задач в анализе структур данных.

Можно ли использовать splay-дерево для range-запросов? Да, через split/join. Чтобы посчитать сумму по диапазону $[l, r]$, делаем $\text{split}(l)$ и $\text{split}(r)$, получаем поддерево с искомыми ключами, в корне которого можно держать агрегированную сумму (как в seg-tree). Эту идею развивает структура Эйлерова обхода поверх splay-деревьев - фундамент link/cut trees.

Коротко

Splay-дерево - самобалансирующееся BST, в котором единственная балансирующая операция $\text{splay}$ продвигает обращённый узел в корень через комбинации шагов zig, zig-zig и zig-zag. Амортизированная сложность $O(\log n)$ на операцию доказывается через potential function $\Phi = \sum \log s(x)$. Дерево автоматически адаптируется к паттерну доступа (working-set, static optimality, dynamic finger) и обходится без служебных полей у узлов. Платой за гибкость становится отсутствие гарантии $O(\log n)$ на конкретную операцию - поэтому в hard real-time системах предпочитают AVL или красно-чёрные деревья, а в адаптивных приложениях splay часто выигрывает на практике.