Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться?
Представим, что мы уже построили дерево на
ключах и теперь нам нужно отвечать на запросы, лежит ли заданный ключ в дереве. Может так оказаться, что пользователя интересует в основном один ключ, и остальные он запрашивает только время от времени. Если ключ лежит далеко от корня, то
запросов могут отнять
времени. Здравый смысл подсказывает, что оценку можно оптимизировать до
, надстроив над деревом кэш. Но этот подход имеет некоторый недостаток гибкости и элегантности.
Сегодня я расскажу о splay-деревьях. Эти деревья не являются перманентно сбалансированными и на отдельных запросах могут работать даже линейное время. Однако, после каждого запроса они меняют свою структуру, что позволяет очень эффективно обрабатывать часто повторяющиеся запросы. Более того, амортизационная стоимость обработки одного запроса у них
, что делает splay-деревья хорошей альтернативой для перманентно сбалансированных собратьев.
В середине восьмидесятых Роберт Тарьян и Даниель Слейтор предложили несколько красивых и эффективных структур данных. Все они имеют несложную базовую структуру и одну-две эвристики, которые их постоянно локально подправляют. Splay-дерево — одна из таких структур.
Splay-дерево — это самобалансирующееся бинарное дерево поиска. Дереву не нужно хранить никакой дополнительной информации, что делает его эффективным по памяти. После каждого обращения, даже поиска, splay-дерево меняет свою структуру.
Ниже я опишу алгоритм, как работает дерево на наборе попарно различных ключей, а потом приведу его анализ.
Для описания структуры дерева нам пригодится простенький класс, описывающий отдельную вершину,
и две вспомогательные процедуры для работы с указателями на родителей.
Основная эвристика splay-дерева — move-to-root. После обращения к любой вершине, она поднимается в корень. Подъем реализуется через повороты вершин. За один поворот, можно поменять местами родителя с ребенком, как показано на рисунке ниже.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/58b/97d/c8b/58b97dc8bf8293538e48a34716f4e1f5.png)
Но просто поворачивать вершину, пока она не станет корнем, недостаточно. Хитрость splay-дерева в том, что при продвижении вершины вверх, расстояние до корня сокращается не только для поднимаемой вершины, но и для всех ее потомков в текущих поддеревьях. Для этого используется техника zig-zig и zig-zag поворотов.
Основная идея zig-zig и zig-zag поворотов, рассмотреть путь от дедушки к ребенку. Если путь идет только по левым детям или только по правым, то такая ситуация называется zig-zig. Как ее обрабатывать показано на рисунке ниже. Сначала повернуть родителя, потом ребенка.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/13c/2ec/397/13c2ec39790be792f792fe393db53be5.png)
В противном случае, мы сначала меняем ребенка с текущим родителем, потом с новым.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/ccf/9f3/f52/ccf9f3f52fea0caa23df9070d4833bc3.png)
Если у вершины дедушки нет, делаем обычный поворот:
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/36e/527/090/36e527090c0e49bf48ba45d20fb780f7.png)
Описанная выше процедура поднятия вершины с помощью zig-zig и zig-zag поворотов является ключевой для splay-дерева.
Примечание. В русском языке термин «splay» перевели как «расширять». Мне кажется, это не очень удачный перевод. Вы берете вершину и тянете ее наверх. В это время все другие вершины уходят вниз, поворачиваясь вокруг нее. Нечто похожее происходит, когда вы выворачиваете футболку. Так что слово «выворачивать» кажется здесь более подходящим.
Процедура поиска в splay-дереве отличается от обычной только на последней стадии: после того, как вершина найдена, мы тянем ее вверх и делаем корнем через процедуру
Чтобы реализовать вставку и удаление ключа, нам потребуются две процедуры:
Процедура
Чтобы вставить очередной ключ, достаточно вызвать
Процедура
Для того, чтобы удалить вершину, нужно поднять ее вверх, а потом слить ее левые и правые поддеревья.
Чтобы splay-дерево поддерживало повторяющиеся ключи, можно поступить двумя способами. Нужно либо каждому ключу сопоставить список, хранящий нужную доп. информацию, либо реализовать процедуру find так, чтобы она возвращала первую в порядке обхода LUR вершину с ключом, большим либо равным заданного.
Заметим, что процедуры удаления, вставки, слияния и разделения деревьев работают за
+ время работы процедуры
Процедура
Для анализа воспользуемся методом физика, про который я рассказывал в статье про амортизационный анализ. Пусть
— размер поддерева
с корнем в вершине
. Рангом вершины
назовем величину
. Наш потенциал будет
.
Будем считать, что фактическое время процедуры
вершины
. Отметим, что это также равно числу элементарных поворотов, которые будут выполнены в ходе процедуры.
Утверждение. Амортизационная стоимость операции
в дереве
с корнем
составляет
.
Доказательство.
Если
— корень, то утверждение очевидно. В противном случае разделим процедуру
После каждого этапа ранг вершины
будет меняться. Пусть изначально ранг составляет
, а после
-ого этапа —
. Для каждого этапа, кроме, быть может, последнего, мы покажем, что амортизационное время на его выполнение можно ограничить сверху величиной
. Для последнего этапа верхняя оценка составит
. Просуммировав верхние оценки и сократив промежуточные значения рангов мы получим требуемое
![](http://habrastorage.org/getpro/habr/post_images/72d/3e4/837/72d3e4837c9cbdce557c78e41a136e51.gif)
Нужно только заметить, что
, а
.
Теперь разберем каждый тип поворота отдельно.
Zig. Может выполняться только один раз, на последнем этапе. Фактическое время
. Посмотрим на рисунок и поймем, что ранги меняются только у вершин
и
.
![](http://habrastorage.org/r/w1560/files/bd9/d53/7e5/bd9d537e58a24dfb94445b704a903153.png)
Значит, амортизационная стоимость составит
. Ранги
и
сокращаются. Исходя из размеров соответствующих поддеревьев применим к формуле
неравенство:
![](http://habrastorage.org/getpro/habr/post_images/0ca/37d/0b1/0ca37d0b18e353c266d5b324d89a156f.gif)
Значит,
.
Zig-zig. Фактическое время
. Заметим, что ранги меняются только у вершин
,
и
.
![](//habrastorage.org/r/w1560/files/566/742/2e5/5667422e5f6a4b17b1936349921a2a62.png)
Тогда амортизационная стоимость
. Ранги
и
можно сократить. Получим, что
. Исходя из размеров поддеревьев применим к формуле
два неравенства:
![](http://habrastorage.org/getpro/habr/post_images/008/61a/f75/00861af757b1c0f16fdd2a82525d278e.gif)
и получим, что
.
Наша цель — показать, что
. Для этого достаточно показать, что
:
![](http://habrastorage.org/getpro/habr/post_images/385/49c/6e6/38549c6e67f5913b05c03db9e23f0966.gif)
Для удобства перенесем ранги в левую часть и будем доказывать
. По определению ранга
. Последнее равенство разобъем на сумму
. Посмотрим на рисунок и поймем, что
.
Факт.
для любых положительных
таких, что
.
Значит,
. Получили требуемое.
Zig-zag.
![](//habrastorage.org/r/w1560/files/fd0/b05/323/fd0b0532300a4e98b6089883319524c8.png)
Аналогично предыдущему случаю запишем амортизационную оценку:
.
Ранги
и
сокращаются. К формуле
применим следующие неравенства:
![](http://habrastorage.org/getpro/habr/post_images/0c5/232/69d/0c523269dbad8d147f278380b9d4cb76.gif)
Значит,
. Это неравенство доказывается аналогично предыдущему случаю.
Таким образом мы разобрали все три случая и получили верхнюю оценку на амортизированное время через ранги.![](http://habrastorage.org/getpro/habr/post_images/a8e/bdf/07e/a8ebdf07e1219a23c6f51afadcf2d768.gif)
Осталось заметить, что ранг любой вершины ограничен логарифмом размера дерева. Из чего следует следующая теорема.
Теорема. Операция
.
На десерт я хотел бы сослаться на википедию и представить здесь несколько интересных фактов про
Теорема о статической оптимальности. Пусть
— число раз, которое был запрошен элемент
. Тогда выполнение
запросов поиска на
.
По сути этот факт сообщает следующее. Пусть мы заранее знаем, в каком количестве будут заданы запросы для различных элементов. Мы строим какое-то конкретное бинарное дерево, чтобы отвечать на эти запросы как можно быстрее. Утверждение сообщает, что с точностью до константы
Теорема о текущем множестве. Пусть
— это число запросов, которое мы уже совершили с момента последнего запроса к элементу
; если еще не обращались, то просто число запросов с самого начала. Тогда время обработки
запросов составит
.
Этот факт формализует мое рассуждение о кэше в начале статьи. По сути он говорит, что в среднем недавно запрошенный элемент не уплывает далеко от корня.
Сканирующая теорема Последовательный доступ (LUR) к элементам
.
Этот факт имеет большое практическое следствие. Вместе с операциями split и merge, он делает
Спасибо за внимание!
UPD.
В комментариях есть резонный вопрос о применимости этого алгоритма на практике. Прежде чем на него ответить, я хочу заметить, что этот пост в первую очередь знакомит читателя с самим алгоритмом и его теоретическими основами. По этой причине вопросы об эффективной реализации, деталях и трюках оптимизации, коих достаточно много, я оставил за пределами статьи.
Исследование производительности и области применения splay-деревьев оказалась темой для десятка статей. Очень оптимистичным выглядит обзор «Performance Analysis of BSTs in System Software» Pfaff, который сравнивает 20 сбалансированных деревьев с различными внутренними представлениями узлов. Тестирование производится на реальных данных для задач управления виртуальной памятью, кэшировании IP-пакетов и разрешении перекрестных ссылок. На виртуальной памяти и перекрестных ссылках splay-деревья проявили себя наилучшим образом; на IP-пакетах уступили место AVL- и красно-черным деревьям. Высокая производительность объясняется особенностью реальных данных. Подробности исследования лучше прочитать в самой статье.
Также можно подробно ознакомиться с отчетом о производительности splay-деревьев и вопросом уменьшения числа поворотов в статье «Reducing Splaying by Taking Advantage of Working Sets» Timi Aho and etc. Список литературы в конце статьи содержит еще несколько отчетов о производительности.
Представим, что мы уже построили дерево на
![](https://habrastorage.org/getpro/habr/post_images/c7f/092/d48/c7f092d481acb49c8a0f96178ceb3119.gif)
![](https://habrastorage.org/getpro/habr/post_images/076/63d/c3c/07663dc3c790b8c5e111597f71b68abc.gif)
![](https://habrastorage.org/getpro/habr/post_images/7be/274/948/7be27494810106e7a26b615c21f37527.gif)
Сегодня я расскажу о splay-деревьях. Эти деревья не являются перманентно сбалансированными и на отдельных запросах могут работать даже линейное время. Однако, после каждого запроса они меняют свою структуру, что позволяет очень эффективно обрабатывать часто повторяющиеся запросы. Более того, амортизационная стоимость обработки одного запроса у них
![](http://habrastorage.org/getpro/habr/post_images/84c/07b/cc9/84c07bcc99d5fc8ab9086ace521ed96a.gif)
Splay-деревья
В середине восьмидесятых Роберт Тарьян и Даниель Слейтор предложили несколько красивых и эффективных структур данных. Все они имеют несложную базовую структуру и одну-две эвристики, которые их постоянно локально подправляют. Splay-дерево — одна из таких структур.
Splay-дерево — это самобалансирующееся бинарное дерево поиска. Дереву не нужно хранить никакой дополнительной информации, что делает его эффективным по памяти. После каждого обращения, даже поиска, splay-дерево меняет свою структуру.
Ниже я опишу алгоритм, как работает дерево на наборе попарно различных ключей, а потом приведу его анализ.
Алгоритм
Для описания структуры дерева нам пригодится простенький класс, описывающий отдельную вершину,
class Node:
def __init__(self, key, left = None, right = None, parent = None):
self.left = left
self.right = right
self.parent = parent
self.key = key
и две вспомогательные процедуры для работы с указателями на родителей.
def set_parent(child, parent):
if child != None:
child.parent = parent
def keep_parent(v):
set_parent(v.left, v)
set_parent(v.right, v)
Основная эвристика splay-дерева — move-to-root. После обращения к любой вершине, она поднимается в корень. Подъем реализуется через повороты вершин. За один поворот, можно поменять местами родителя с ребенком, как показано на рисунке ниже.
![](https://habrastorage.org/getpro/habr/post_images/58b/97d/c8b/58b97dc8bf8293538e48a34716f4e1f5.png)
def rotate(parent, child):
gparent = parent.parent
if gparent != None:
if gparent.left == parent:
gparent.left = child
else:
gparent.right = child
if parent.left == child:
parent.left, child.right = child.right, parent
else:
parent.right, child.left = child.left, parent
keep_parent(child)
keep_parent(parent)
child.parent = gparent
Но просто поворачивать вершину, пока она не станет корнем, недостаточно. Хитрость splay-дерева в том, что при продвижении вершины вверх, расстояние до корня сокращается не только для поднимаемой вершины, но и для всех ее потомков в текущих поддеревьях. Для этого используется техника zig-zig и zig-zag поворотов.
Основная идея zig-zig и zig-zag поворотов, рассмотреть путь от дедушки к ребенку. Если путь идет только по левым детям или только по правым, то такая ситуация называется zig-zig. Как ее обрабатывать показано на рисунке ниже. Сначала повернуть родителя, потом ребенка.
![](https://habrastorage.org/getpro/habr/post_images/13c/2ec/397/13c2ec39790be792f792fe393db53be5.png)
В противном случае, мы сначала меняем ребенка с текущим родителем, потом с новым.
![](https://habrastorage.org/getpro/habr/post_images/ccf/9f3/f52/ccf9f3f52fea0caa23df9070d4833bc3.png)
Если у вершины дедушки нет, делаем обычный поворот:
![](https://habrastorage.org/getpro/habr/post_images/36e/527/090/36e527090c0e49bf48ba45d20fb780f7.png)
Описанная выше процедура поднятия вершины с помощью zig-zig и zig-zag поворотов является ключевой для splay-дерева.
Примечание. В русском языке термин «splay» перевели как «расширять». Мне кажется, это не очень удачный перевод. Вы берете вершину и тянете ее наверх. В это время все другие вершины уходят вниз, поворачиваясь вокруг нее. Нечто похожее происходит, когда вы выворачиваете футболку. Так что слово «выворачивать» кажется здесь более подходящим.
def splay(v):
if v.parent == None:
return v
parent = v.parent
gparent = parent.parent
if gparent == None:
rotate(parent, v)
return v
else:
zigzig = (gparent.left == parent) == (parent.left == v)
if zigzig:
rotate(gparent, parent)
rotate(parent, v)
else:
rotate(parent, v)
rotate(gparent, v)
return splay(v)
Процедура поиска в splay-дереве отличается от обычной только на последней стадии: после того, как вершина найдена, мы тянем ее вверх и делаем корнем через процедуру
splay
.def find(v, key):
if v == None:
return None
if key == v.key:
return splay(v)
if key < v.key and v.left != None:
return find(v.left, key)
if key > v.key and v.right != None:
return find(v.right, key)
return splay(v)
Чтобы реализовать вставку и удаление ключа, нам потребуются две процедуры:
split
и merge
(разрезать и слить). Процедура
split
получает на вход ключ key
и делит дерево на два. В одном дереве все значения меньше ключа key
, а в другом — больше. Реализуется она просто. Нужно через find
найти ближайшую к ключу вершину, вытянуть ее вверх и потом отрезать либо левое, либо правое поддерево (либо оба).def split(root, key):
if root == None:
return None, None
root = find(root, key)
if root.key == key:
set_parent(root.left, None)
set_parent(root.right, None)
return root.left, root.right
if root.key < key:
right, root.right = root.right, None
set_parent(right, None)
return root, right
else:
left, root.left = root.left, None
set_parent(left, None)
return left, root
Чтобы вставить очередной ключ, достаточно вызвать
split
по нему, а затем сделать новую вершину-корень, у которой поддеревьями будет результат split
-а.def insert(root, key):
left, right = split(root, key)
root = Node(key, left, right)
keep_parent(root)
return root
Процедура
merge
получает на вход два дерева: левое left
и правое right
. Для корректной работы, ключи дерева left
должны быть меньше ключей дерева right
. Здесь мы берем вершину с наименьшим ключом правого дерева right
и тянем ее вверх. После этого в качестве левого поддерева присоединяем дерево left
.def merge(left, right):
if right == None:
return left
if left == None:
return right
right = find(right, left.key)
right.left, left.parent = left, right
return right
Для того, чтобы удалить вершину, нужно поднять ее вверх, а потом слить ее левые и правые поддеревья.
def remove(root, key):
root = find(root, key)
set_parent(root.left, None)
set_parent(root.right, None)
return merge(root.left, root.right)
Чтобы splay-дерево поддерживало повторяющиеся ключи, можно поступить двумя способами. Нужно либо каждому ключу сопоставить список, хранящий нужную доп. информацию, либо реализовать процедуру find так, чтобы она возвращала первую в порядке обхода LUR вершину с ключом, большим либо равным заданного.
Анализ
Заметим, что процедуры удаления, вставки, слияния и разделения деревьев работают за
![](http://habrastorage.org/getpro/habr/post_images/ec7/176/ecf/ec7176ecffb2f187d5ef0d0d24ffdbd4.gif)
find
.Процедура
find
работает пропорционально глубине искомой вершины в дереве. По завершении поиска запускается процедура splay
, которая тоже работает пропорционально глубине вершины. Таким образом, достаточно оценить время работы процедуры splay
.Для анализа воспользуемся методом физика, про который я рассказывал в статье про амортизационный анализ. Пусть
![](http://habrastorage.org/getpro/habr/post_images/2c4/55f/6c3/2c455f6c331507d8415d138c126d5cd1.gif)
![](http://habrastorage.org/getpro/habr/post_images/801/e91/678/801e916781182638bdd30f434f6dd79f.gif)
![](http://habrastorage.org/getpro/habr/post_images/2a4/a15/263/2a4a15263185920396d9b74a66fda10e.gif)
![](http://habrastorage.org/getpro/habr/post_images/01e/fed/dbf/01efeddbf29cf53eddad0eb121c3865c.gif)
Будем считать, что фактическое время процедуры
splay(v)
равно глубине Утверждение. Амортизационная стоимость операции
splay
от вершины ![](http://habrastorage.org/getpro/habr/post_images/b94/550/354/b94550354872977b0f0aad8cda86789e.gif)
![](http://habrastorage.org/getpro/habr/post_images/bac/598/191/bac5981912a4b3785f398a37163010ec.gif)
Доказательство.
Если
splay(v)
на этапы. В ходе каждого этапа выполняется один из трех поворотов: zig, zig-zig или zig-zag. На простой поворот уходит единица времени, на zig-zig и zig-zag — две единицы.После каждого этапа ранг вершины
![](http://habrastorage.org/getpro/habr/post_images/bd2/e8c/4de/bd2e8c4deee380873258074067f47a79.gif)
![](http://habrastorage.org/getpro/habr/post_images/45a/141/2de/45a1412deeddf95d0291a61419916399.gif)
![](http://habrastorage.org/getpro/habr/post_images/514/7e6/520/5147e652057fc82f5cc918ad29f95543.gif)
![](http://habrastorage.org/getpro/habr/post_images/3a7/c5a/d43/3a7c5ad43334e60bfd005218c4a6cf67.gif)
![](http://habrastorage.org/getpro/habr/post_images/72d/3e4/837/72d3e4837c9cbdce557c78e41a136e51.gif)
Нужно только заметить, что
![](http://habrastorage.org/getpro/habr/post_images/3d4/903/c4a/3d4903c4a6ab562fa149407b12cbdd95.gif)
![](http://habrastorage.org/getpro/habr/post_images/a10/2e6/672/a102e6672264a72c4d01f4c1ef352345.gif)
Теперь разберем каждый тип поворота отдельно.
Zig. Может выполняться только один раз, на последнем этапе. Фактическое время
![](http://habrastorage.org/getpro/habr/post_images/26f/ff1/377/26fff1377fd5ee7a18d590a322203e05.gif)
![](http://habrastorage.org/files/bd9/d53/7e5/bd9d537e58a24dfb94445b704a903153.png)
Значит, амортизационная стоимость составит
![](http://habrastorage.org/getpro/habr/post_images/e61/061/e90/e61061e90cf933cf6ec28f8d25e905d7.gif)
![](http://habrastorage.org/getpro/habr/post_images/155/bde/9f5/155bde9f50a1332adbefa9c833ae068f.gif)
![](http://habrastorage.org/getpro/habr/post_images/ad2/d15/a8d/ad2d15a8df39e0b455d90f44a350d356.gif)
![](http://habrastorage.org/getpro/habr/post_images/270/cbb/bb6/270cbbbb6cb0b4c0634e86f443bd3ab6.gif)
![](http://habrastorage.org/getpro/habr/post_images/0ca/37d/0b1/0ca37d0b18e353c266d5b324d89a156f.gif)
Значит,
![](http://habrastorage.org/getpro/habr/post_images/e8e/aea/72f/e8eaea72f1417fc4e5e0d7a0cc887ef1.gif)
Zig-zig. Фактическое время
![](http://habrastorage.org/getpro/habr/post_images/95c/007/330/95c0073302d8e83f0658373bf031d628.gif)
![](http://habrastorage.org/getpro/habr/post_images/778/167/ba0/778167ba0bfe8d797c1444241533f806.gif)
![](http://habrastorage.org/getpro/habr/post_images/4f9/ca1/b1c/4f9ca1b1c8029535c88032fbe0b24b60.gif)
![](http://habrastorage.org/getpro/habr/post_images/8ca/ebe/078/8caebe078b8f5a33590e85caea5439cd.gif)
![](http://habrastorage.org/files/566/742/2e5/5667422e5f6a4b17b1936349921a2a62.png)
Тогда амортизационная стоимость
![](http://habrastorage.org/getpro/habr/post_images/f88/07b/f37/f8807bf37fe6b7b3233fef522b691a4a.gif)
![](http://habrastorage.org/getpro/habr/post_images/155/bde/9f5/155bde9f50a1332adbefa9c833ae068f.gif)
![](http://habrastorage.org/getpro/habr/post_images/8ca/ebe/078/8caebe078b8f5a33590e85caea5439cd.gif)
![](http://habrastorage.org/getpro/habr/post_images/9e6/f72/cc4/9e6f72cc4496cad479eee6dfb081b61c.gif)
![](http://habrastorage.org/getpro/habr/post_images/270/cbb/bb6/270cbbbb6cb0b4c0634e86f443bd3ab6.gif)
![](http://habrastorage.org/getpro/habr/post_images/008/61a/f75/00861af757b1c0f16fdd2a82525d278e.gif)
и получим, что
![](http://habrastorage.org/getpro/habr/post_images/e75/31c/f9f/e7531cf9f42d16323412064c7f4f5fe6.gif)
Наша цель — показать, что
![](http://habrastorage.org/getpro/habr/post_images/d52/059/7a0/d520597a0b03a29b8c707e8c848c0c3c.gif)
![](http://habrastorage.org/getpro/habr/post_images/da2/0bd/041/da20bd0413ddd7abb2c6a1124a70ed1f.gif)
![](http://habrastorage.org/getpro/habr/post_images/385/49c/6e6/38549c6e67f5913b05c03db9e23f0966.gif)
Для удобства перенесем ранги в левую часть и будем доказывать
![](http://habrastorage.org/getpro/habr/post_images/8d1/be0/29f/8d1be029f449db8442cfb9b5e81cd7f6.gif)
![](http://habrastorage.org/getpro/habr/post_images/ab1/b92/dcc/ab1b92dcc990d3ac0f39df4e4ece7ec0.gif)
![](http://habrastorage.org/getpro/habr/post_images/269/10c/32f/26910c32f49a0473c0bf8b9aea4d6158.gif)
![](http://habrastorage.org/getpro/habr/post_images/f8f/dbd/a6d/f8fdbda6d98e4b55cef1518928558774.gif)
Факт.
![](http://habrastorage.org/getpro/habr/post_images/cb8/e8e/c07/cb8e8ec07a4a7872b6acaf707d6e673f.gif)
![](http://habrastorage.org/getpro/habr/post_images/c80/d13/d58/c80d13d587a00fca58b429e785e3c06a.gif)
![](http://habrastorage.org/getpro/habr/post_images/76b/3b1/ea4/76b3b1ea4f0c87f8fc93e7f66faf333b.gif)
Значит,
![](http://habrastorage.org/getpro/habr/post_images/a93/276/f12/a93276f12dd9474eb7fef7a83748cebf.gif)
Zig-zag.
![](http://habrastorage.org/files/fd0/b05/323/fd0b0532300a4e98b6089883319524c8.png)
Аналогично предыдущему случаю запишем амортизационную оценку:
![](http://habrastorage.org/getpro/habr/post_images/f88/07b/f37/f8807bf37fe6b7b3233fef522b691a4a.gif)
Ранги
![](http://habrastorage.org/getpro/habr/post_images/155/bde/9f5/155bde9f50a1332adbefa9c833ae068f.gif)
![](http://habrastorage.org/getpro/habr/post_images/8ca/ebe/078/8caebe078b8f5a33590e85caea5439cd.gif)
![](http://habrastorage.org/getpro/habr/post_images/270/cbb/bb6/270cbbbb6cb0b4c0634e86f443bd3ab6.gif)
![](http://habrastorage.org/getpro/habr/post_images/0c5/232/69d/0c523269dbad8d147f278380b9d4cb76.gif)
Значит,
![](http://habrastorage.org/getpro/habr/post_images/11e/019/6f0/11e0196f041a65b9712d2128d106eeaf.gif)
Таким образом мы разобрали все три случая и получили верхнюю оценку на амортизированное время через ранги.
![](http://habrastorage.org/getpro/habr/post_images/a8e/bdf/07e/a8ebdf07e1219a23c6f51afadcf2d768.gif)
Осталось заметить, что ранг любой вершины ограничен логарифмом размера дерева. Из чего следует следующая теорема.
Теорема. Операция
splay
амортизационно выполняется за ![](http://habrastorage.org/getpro/habr/post_images/84c/07b/cc9/84c07bcc99d5fc8ab9086ace521ed96a.gif)
Другие метрики и свойства
На десерт я хотел бы сослаться на википедию и представить здесь несколько интересных фактов про
splay
-деревья.Теорема о статической оптимальности. Пусть
![](http://habrastorage.org/getpro/habr/post_images/cad/4e8/f95/cad4e8f9585700a0a979e4d098851bb4.gif)
![](http://habrastorage.org/getpro/habr/post_images/882/839/fd0/882839fd0d8c0796ef0f881d89ac3705.gif)
![](http://habrastorage.org/getpro/habr/post_images/601/5f7/e7e/6015f7e7e19971bf1372e01171eaadcb.gif)
splay
-дереве выполняется за ![](http://habrastorage.org/getpro/habr/post_images/4e4/afc/38a/4e4afc38a83dfc386be50875ee0dd12f.gif)
По сути этот факт сообщает следующее. Пусть мы заранее знаем, в каком количестве будут заданы запросы для различных элементов. Мы строим какое-то конкретное бинарное дерево, чтобы отвечать на эти запросы как можно быстрее. Утверждение сообщает, что с точностью до константы
splay
-дерево будет амортизационно работать не хуже, чем самое оптимальное фиксированное дерево, которое мы можем придумать. Теорема о текущем множестве. Пусть
![](http://habrastorage.org/getpro/habr/post_images/41c/9fd/590/41c9fd5903fa785884a1325457399279.gif)
![](http://habrastorage.org/getpro/habr/post_images/12f/ee3/928/12fee3928922dbe461d4bd49abc7df24.gif)
![](http://habrastorage.org/getpro/habr/post_images/601/5f7/e7e/6015f7e7e19971bf1372e01171eaadcb.gif)
![](http://habrastorage.org/getpro/habr/post_images/65d/250/85a/65d25085aec30c33ef47e960ff608e05.gif)
Этот факт формализует мое рассуждение о кэше в начале статьи. По сути он говорит, что в среднем недавно запрошенный элемент не уплывает далеко от корня.
Сканирующая теорема Последовательный доступ (LUR) к элементам
splay
-дерева выполняется за ![](http://habrastorage.org/getpro/habr/post_images/39a/ed9/498/39aed9498a90431e37a7b32ffe2338cd.gif)
Этот факт имеет большое практическое следствие. Вместе с операциями split и merge, он делает
splay
-деревья отличной основой для структуры данных rope
. Подробнее про нее можно прочитать постах Хабра Ropes — быстрые строки и Моноиды и их приложения....Спасибо за внимание!
Литература
- Tarjan «Data Structures and Networks Algorithms»
- Sleator, Daniel D.; Tarjan, Robert E. (1985), «Self-Adjusting Binary Search Trees»
UPD.
Прагматику на заметку
В комментариях есть резонный вопрос о применимости этого алгоритма на практике. Прежде чем на него ответить, я хочу заметить, что этот пост в первую очередь знакомит читателя с самим алгоритмом и его теоретическими основами. По этой причине вопросы об эффективной реализации, деталях и трюках оптимизации, коих достаточно много, я оставил за пределами статьи.
Исследование производительности и области применения splay-деревьев оказалась темой для десятка статей. Очень оптимистичным выглядит обзор «Performance Analysis of BSTs in System Software» Pfaff, который сравнивает 20 сбалансированных деревьев с различными внутренними представлениями узлов. Тестирование производится на реальных данных для задач управления виртуальной памятью, кэшировании IP-пакетов и разрешении перекрестных ссылок. На виртуальной памяти и перекрестных ссылках splay-деревья проявили себя наилучшим образом; на IP-пакетах уступили место AVL- и красно-черным деревьям. Высокая производительность объясняется особенностью реальных данных. Подробности исследования лучше прочитать в самой статье.
Также можно подробно ознакомиться с отчетом о производительности splay-деревьев и вопросом уменьшения числа поворотов в статье «Reducing Splaying by Taking Advantage of Working Sets» Timi Aho and etc. Список литературы в конце статьи содержит еще несколько отчетов о производительности.