Splay-деревья

в 8:38, , рубрики: Без рубрики

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

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

Сегодня я расскажу о splay-деревьях. Эти деревья не являются перманентно сбалансированными и на отдельных запросах могут работать даже линейное время. Однако, после каждого запроса они меняют свою структуру, что позволяет очень эффективно обрабатывать часто повторяющиеся запросы. Более того, амортизационная стоимость обработки одного запроса у них 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. После обращения к любой вершине, она поднимается в корень. Подъем реализуется через повороты вершин. За один поворот, можно поменять местами родителя с ребенком, как показано на рисунке ниже.

Splay деревья

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

Splay деревья

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

Splay деревья

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

Splay деревья

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

Анализ

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

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

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

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

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

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

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

Splay деревья

Нужно только заметить, что Splay деревья, а Splay деревья.

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

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

Splay деревья

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

Splay деревья

Значит, Splay деревья.

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

Splay деревья

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

Splay деревья

и получим, что Splay деревья.

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

Splay деревья

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

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

Значит, Splay деревья. Получили требуемое.

Zig-zag.

Splay деревья

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

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

Splay деревья

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

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

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

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

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

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

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

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

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

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

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

Этот факт имеет большое практическое следствие. Вместе с операциями split и merge, он делает splay-деревья отличной основой для структуры данных rope. Подробнее про нее можно прочитать постах Хабра Ropes — быстрые строки и Моноиды и их приложения....

Спасибо за внимание!

Литература

  • Tarjan «Data Structures and Networks Algorithms»
  • Sleator, Daniel D.; Tarjan, Robert E. (1985), «Self-Adjusting Binary Search Trees»

Автор: SeptiM

Источник

Поделиться

* - обязательные к заполнению поля