Splay-деревья

  • Tutorial
Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться?

Представим, что мы уже построили дерево на ключах и теперь нам нужно отвечать на запросы, лежит ли заданный ключ в дереве. Может так оказаться, что пользователя интересует в основном один ключ, и остальные он запрашивает только время от времени. Если ключ лежит далеко от корня, то запросов могут отнять времени. Здравый смысл подсказывает, что оценку можно оптимизировать до , надстроив над деревом кэш. Но этот подход имеет некоторый недостаток гибкости и элегантности.

Сегодня я расскажу о splay-деревьях. Эти деревья не являются перманентно сбалансированными и на отдельных запросах могут работать даже линейное время. Однако, после каждого запроса они меняют свою структуру, что позволяет очень эффективно обрабатывать часто повторяющиеся запросы. Более того, амортизационная стоимость обработки одного запроса у них , что делает splay-деревья хорошей альтернативой для перманентно сбалансированных собратьев.

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. После обращения к любой вершине, она поднимается в корень. Подъем реализуется через повороты вершин. За один поворот, можно поменять местами родителя с ребенком, как показано на рисунке ниже.



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. Как ее обрабатывать показано на рисунке ниже. Сначала повернуть родителя, потом ребенка.



В противном случае, мы сначала меняем ребенка с текущим родителем, потом с новым.



Если у вершины дедушки нет, делаем обычный поворот:



Описанная выше процедура поднятия вершины с помощью 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 вершину с ключом, большим либо равным заданного.

Анализ


Заметим, что процедуры удаления, вставки, слияния и разделения деревьев работают за + время работы процедуры find.

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

Для анализа воспользуемся методом физика, про который я рассказывал в статье про амортизационный анализ. Пусть — размер поддерева с корнем в вершине . Рангом вершины назовем величину . Наш потенциал будет .

Будем считать, что фактическое время процедуры splay(v) равно глубине вершины . Отметим, что это также равно числу элементарных поворотов, которые будут выполнены в ходе процедуры.

Утверждение. Амортизационная стоимость операции splay от вершины в дереве с корнем составляет .

Доказательство.
Если — корень, то утверждение очевидно. В противном случае разделим процедуру splay(v) на этапы. В ходе каждого этапа выполняется один из трех поворотов: zig, zig-zig или zig-zag. На простой поворот уходит единица времени, на zig-zig и zig-zag — две единицы.

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



Нужно только заметить, что , а .

Теперь разберем каждый тип поворота отдельно.

Zig. Может выполняться только один раз, на последнем этапе. Фактическое время . Посмотрим на рисунок и поймем, что ранги меняются только у вершин и .



Значит, амортизационная стоимость составит . Ранги и сокращаются. Исходя из размеров соответствующих поддеревьев применим к формуле неравенство:



Значит, .

Zig-zig. Фактическое время . Заметим, что ранги меняются только у вершин , и .



Тогда амортизационная стоимость . Ранги и можно сократить. Получим, что . Исходя из размеров поддеревьев применим к формуле два неравенства:



и получим, что .

Наша цель — показать, что . Для этого достаточно показать, что :



Для удобства перенесем ранги в левую часть и будем доказывать . По определению ранга . Последнее равенство разобъем на сумму . Посмотрим на рисунок и поймем, что .

Факт. для любых положительных таких, что .

Значит, . Получили требуемое.

Zig-zag.



Аналогично предыдущему случаю запишем амортизационную оценку: .

Ранги и сокращаются. К формуле применим следующие неравенства:



Значит, . Это неравенство доказывается аналогично предыдущему случаю.

Таким образом мы разобрали все три случая и получили верхнюю оценку на амортизированное время через ранги.

Осталось заметить, что ранг любой вершины ограничен логарифмом размера дерева. Из чего следует следующая теорема.

Теорема. Операция splay амортизационно выполняется за .

Другие метрики и свойства


На десерт я хотел бы сослаться на википедию и представить здесь несколько интересных фактов про splay-деревья.

Теорема о статической оптимальности. Пусть — число раз, которое был запрошен элемент . Тогда выполнение запросов поиска на splay-дереве выполняется за .

По сути этот факт сообщает следующее. Пусть мы заранее знаем, в каком количестве будут заданы запросы для различных элементов. Мы строим какое-то конкретное бинарное дерево, чтобы отвечать на эти запросы как можно быстрее. Утверждение сообщает, что с точностью до константы splay-дерево будет амортизационно работать не хуже, чем самое оптимальное фиксированное дерево, которое мы можем придумать.

Теорема о текущем множестве. Пусть — это число запросов, которое мы уже совершили с момента последнего запроса к элементу ; если еще не обращались, то просто число запросов с самого начала. Тогда время обработки запросов составит .

Этот факт формализует мое рассуждение о кэше в начале статьи. По сути он говорит, что в среднем недавно запрошенный элемент не уплывает далеко от корня.

Сканирующая теорема Последовательный доступ (LUR) к элементам splay-дерева выполняется за .

Этот факт имеет большое практическое следствие. Вместе с операциями 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. Список литературы в конце статьи содержит еще несколько отчетов о производительности.
Образовательные проекты JetBrains
192,97
Компания
Поделиться публикацией

Похожие публикации

Комментарии 26

    +1
    С практической точки зрения, ворочать структуру при каждом запросе — сомнительная идея.
      0
      Смотря сколько запросов и сколько обновлений.
        +3
        У каждого инструмента есть своя область применения. Splay-деревья ведут себя хорошо при последовательной обработке большого набора запросов с произвольным распределением. Они экономичны в плане количества информации, которую требуется хранить в узлах. Кроме того, splay-дерево — это сливаемая структура данных.

        С другой стороны я согласен, что постоянное изменение структуры не делает их привлекательными для параллельного или чисто-функционального программирования. Чтобы что-то получить, нужно чем-то расплатиться.
          +6
          Имеет смысл добавить это в статью. Приведите примеры таких запросов. Мне кажется, это было бы полезнее, чем доказательства теор. результатов — я готов поверить на слово, что вы их не перевираете :)
            0
            Добавил ссылку на обзор. Splay-деревья сравнивали с красно-черными и AVL-деревьями на реальных данных. Можете посмотреть таблицы.

            Вам анализ не нужен, кому-то интересен, а у кого-то это splay-деревья с анализом — билет в экзамене.
              0
              Простите, а у кого такое билетом в экзамене? Просто интересна презентативная выборка заведений.
                0
                Провокационный вопрос: прибегут, забанят за рекламу =)

                Для школьников: ЛКШ
                Для студентов: МГУ, КТ ИТМО, Академический ун-т, ШАД, CS Center. Знающие могут дополнить список.
                  0
                  Все в столичных кругах по сути: СПб, Москва. А за ее пределами медведи с косами ходют и на балалайке играют.
                    0
                    Я сомневаюсь, что и в перечисленных заведениях конкретно такой вопрос есть на экзамене, больно специфично. Ну, может, где-то в одном месте есть преподаватель-любитель этой структуры данных.

                    А формально курс «Алгоритмы и структуры данных» с проработкой темы на различной глубине есть почти везде, где его можно ожидать.
                      0
                      Программы у многих заведений открыты. Некоторые даже видеозаписи выкладывают. Если Вы сомневаетесь, что лекционный материал идет на экзамен… ну, сомневайтесь.
                        0
                        В Яндексе, похоже, есть, и в вашем вузе, надо понимать. У нас Бауманке такие вещи идут на экзамен без формального доказательства, только результаты, на отлично — пара вопросов «на понимание».
                          0
                          Да, вы правы — алгоритмы и структуры есть практически в каждом техновузе, с разных сторон IT. И хорошо, что вы подметили про глубину — с ней то и возникает основная проблема. В зависимости от вида сбоку грабель — для каждых грабель — разная она. У меня допустим splay именно не было, всего лишь основы основ и фундаментальные кирпичики.
          +2
          Однако в компиляторах, например, GCC, это одна из основных структур данных. Splay-tree там используется при трансформации из AST в трех-адресный код. Пример использования: github.com/mirrors/gcc/blob/master/gcc/omp-low.c
            0
            Привет от коллег по бранчу gomp-4_0-branch :)
          +5
          статья в лучших и всего 4 комментария. Верный признак того что написанно умно но никто ничего не понял )
            +1
            Меня всегда беспокоят алгоритмы, в которых о константах думают свысока. Например, запись в ответ на запрос чтения — это же ужасно. Особенно, если это несколько записей.

            На практике пренебрежение константами превращается в ужасающего едва ворочающегося монстра, у которого o(logn), но такие константы, что до времён, когда логарифм становится важным, просто не доходят.
              +1
              В теории есть алгоритм Левина, который решает любую задачу за асимптотически оптимальное время. Он перебирает все возможные программы и запускает их параллельно. Но константа там большая, да…

              По поводу практической части. Да, действительно, каждый раз делать splay — это печально. Начиная с 2000 люди предложили несколько эвристик, которые позволяют оптимизировать работу splay-дерева. Кое-каких результатов на практике добились. Я видимо напишу заметку-дополнение как ответ этому комментарию и одному выше, что хорошего здесь происходило.
              +1
              Можно пояснить следующие моменты?

              1. Если у нас есть априорные частоты запросов; в принципе, мы сразу можем построить ДДП с оптимальной глубиной.
              2. Апостериорные частоты, т.е. мы набираем статистику по ходу обращений к дереву, заодно и вращаем его, оптимизируя под текущее распределение.
              3. Скользящая статистика. Предполагается, что история запросов постепенно теряет актуальность.

              В первом случае мы можем отсортировать ключи по возрастанию/убыванию веса (в зависимости от того, как будем строить дерево: добавлять листья или наращивать корень), построим обычное несбалансированное ДДП — его вид будет соответствовать коду Фано.
              А если постараться, то и код Хаффмана так же делается.
              Splay tree здесь, как видно, не при чём.

              В третьем случае, — если придерживаться политики MRU (most recently used), вытаскивать свежезапрошенный ключ на самый верх и затем пусть он тонет, — размер окна истории не поддаётся контролю, а если правильно подобрать запросы, то дерево выродится в линейный список, и в нужный момент мы выстрелим, запросив самый хвостик.
              Или splay tree защищено от таких выстрелов, и какую-то минимальную сбалансированность гарантирует?

              Во втором случае нам или нужна таблица частот (счётчики обращений) для каждого ключа, или у нас не честное MFU (most frequently used), а всё то же MRU.
              Или мы закладываемся на то, что при «хороших» последовательностях запросов политики MFU и MRU должны давать близкие результаты?
                0
                Можно. =)

                1. Если все известно заранее, то splay дерево не нужно. Мне кажется, что решение должно быть каким-то таким. Берем ключ такой, что сумма частот слева и справа от него меньше половины. Делаем его корнем. Строим поддеревья рекурсивно. С точностью до константы, это дерево точно будет оптимальным.

                Хаффман, если что, меняет порядок ключей. Так что его технику использовать напрямую не получится.

                2 (и 3). Мне пока не очень понятно, как именно у вас происходит балансировка. Кроме того, статистика — это доп. информация, которую надо хранить. В AVL, красно-черных деревьях достаточно одного-двух битов доп. информации, в splay — нуля.

                3. Нет, от тяжелых запросов деревья не защищены. В некоторых случаях делают splay через раз, или подбрасывают монетку, делать ли splay. Но вообще, такое может случиться. Если нужны быстрые ответы на единичные запросы, лучше использовать другие деревья: AVL, B, красно-черные.
                  0
                  Если правильно распорядиться Хаффманом, то порядок ключей не изменится.
                  Единственная сложность в том, что при равномерном распределении все ключи должны были бы находиться на одинаковой глубине, а в ДДП в любом случае корневой ключ имеет преимущество.
                  Как это представить в коде Хаффмана, я ещё не придумал, но истина где-то рядом.
                  Итак, схема примерно такая.
                  1) строим код Хаффмана в соответствии с частотами
                  2) забываем про нолики и единички, нас интересует только длина кодов
                  3) располагаем ключи по порядку
                  4) рисуем над ними дерево, так, что каждый ключ оказывается на той глубине, которая соответствует длине его кода
                    0
                    Я думаю, Вам надо провести практическое исследование. Нагенерируйте разные последовательности запросов, возьмите что-то из реальной жизни и протестируйте это на разных деревьях, в том числе, придуманных Вами. Потом можете рассказать, что у Вас получилось в отдельном посте на Хабре.
                    0
                    Про балансировку. Вот мне как раз и непонятно.
                    Процедура splay вытягивает найденный узел наверх, то есть, фактически, мы ведём MRU-список.
                    (А бомба выглядит очень просто, кстати. Опросим все ключи в порядке возрастания, а потом опросим самый первый ключ).

                    Если бы каждый узел хранил счётчик обращений, то мы могли бы поступать более интеллектуально: поднимать обновлённые узлы над своими (пока ещё) менее вероятными соседями, а не до самого корня.
                    Тем самым получим адаптивный код Фано. До кода Хаффмана не дотянемся, да и бог с ним.

                    Чтобы деградировать историю, — проще всего прибегнуть к экспоненциальному скользящему среднему.
                    Тут вес узла — это не сумма обращений за всю историю, а взвешенная сумма с коэффициентами. убывающими по экспоненциальному закону. Т.е. если касались в моменты T=1, 5, 7, а сейчас момент T=10, то вес будет a^(10-7) + a^(10-5) + a^(10-1) где 0<a<1.
                    Считать ЭСС очень удобно, потому что в каждый момент времени достаточно обновлять вес по закону W(t) = W(t-1)*a + dW.
                    Решение в лоб потребовало бы пересчитывать вес всех узлов дерева, но, чтобы избежать это, проще приписать каждому узлу его вес и момент последнего обновления.
                    Тогда пересчёт веса будет выглядеть так: W(t) = W(t-t0)*a^(t-t0) + dW
                    где dW = 1, если узел «был найден» и = 0, если это соседний узел, с которым мы решаем — проворачивать дерево или нет.
                    То есть, в узле, помимо ключа, хранится целое число (номер отсчёта) и вещественное (вес на тот момент).

                    Но это всё «чистые математические» подходы.
                    Если принять меры против вырождения splay-деревьев (случайное перетряхивание или отслеживание дисбаланса, как в AVL), то выгода от простоты структуры принесёт ощутимые плоды.
                    Чем меньше возни и чем меньше памяти, тем быстрее, — даже если количество итераций будет больше (в пределах логарифма).
                      +1
                      Ну и последнее, что хотел сказать: обычное дерево — не cache friendly.
                      Априорный частотный анализ позволил бы разместить наиболее популярные ключи (первые ярусы дерева) в одной странице.
                      Апостериорный — MRU или MFU, — ясное дело, потребует перемещения ключей, а это дорогое удовольствие.

                      Если дерево по-настоящему большое, и мы хотим выжать все оптимизационные соки из него, то лучше, всё-таки, взять априорную статистику и выстроить структуру по-хаффмановски, а в памяти расположить по-ярусно. Да и вообще подумать в сторону Б-деревьев.
                    0
                    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)

                    Завершающий функцию return гарантирует, что если поиск неудачен, то последняя просмотренная вершина будет «выдернута» наверх. Это зачем такое?
                      0
                      Представьте, что в какой-то момент дерево выстроилось в односвязный список. Ключ с наименьшим значением в самом низу. Пусть все запросы спрашивают условно минус бесконечность. Без splay-а каждый запрос будет обрабатываться за линейное время. А так, мы выдергиваем один из ближайших элементов наверх и в следующий раз нам не придется лезть глубоко.
                        0
                        Разумно. Спасибо!

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое