Деревья поиска. АВЛ-деревья

Ты не заметишь этот миг, лишь только завтра поутру

Оглавление

Большие объёмы данных требуют особых подходов к задаче поиска. Если для нахождения элемента среди пары сотен элементов за линейное время достаточно хорошо, то когда речь идёт о тысячах и миллионах элементов, линейное время оказывается неоправданно большим. Можно воспользоваться известным нам бинарным поиском или даже его адаптацией галопированием. Но и это оказывается неэффективно при работе с данными, не влезающими в оперативную память. Действительно, пусть у нас есть файл размера 1 Гб с отсортированными данными. Пусть буфер чтения составляет 1 Кб. Тогда для бинарного поиска потребуется \(\log\frac{2^{30}}{2^{10}} = \log 2^{20} = 20\) чтений с диска. Это очень много. Давайте рассмотрим структуры, позволяющие искать быстрее и использовать компактные индексы по данным.

Деревья поиска

Арностью дерева будем называть количество число \(k\) такое, что для любой вершины дерева количество сыновей этой вершины не превосходит \(k\). В общем случае можно считать, что для любой вершины количество сыновей строго равно \(k\), отсутствующих сыновей можно заменить пустыми поддеревьями \(\varnothing\).

В общем случае для \(k\)-арного дерева для любой вершины \(v\) обозначим поддеревья её сыновей через \(T(v, i)\), где \(i \in k\). Будем называть такое дерево деревом поиска, если в каждой вершине \(v\) хранится неубывающий набор из \(k - 1\) ключа: \({v_i \colon 0 < i < k }\), такой что для любого \(0 < i < k\) ключи элементов \(i-1\) поддерева \(T(v, i - 1)\) не превосходят \(v_i\), а ключи элементов поддерева \(T(v, i)\) не меньше \(v_i\).

5-арный узел дерева поиска
Рис. 1. 5-арный узел дерева поиска

Для начала ограничим ветвистость рассматриваемых деревьев до \(2\). Деревья с большей ветвистостью обычно называются B-деревьями и будут рассматриваться в другой статье. Перепишем определение дерева поиска для бинарного случая, переведя набор ключей в понятие отображения.

Двоичное дерево будем называть двоичным деревом поиска, если для каждой вершины дерева \(u\) определено отображение в линейно упорядоченное множество \(k(u)\), при этом для любой вершины из дерева её левого сына образ этого отображения меньше или равен образа вершины \(u\), а для правого дерева выполнено аналогичное неравенство со знаком больше или равно. То есть:

\[ \forall u \in T \implies (\forall v \in T_{u_\ell} \implies v \leqslant u) \land (\forall v \in T_{u_r} \implies v \geqslant u) \]

В качестве примера можно рассмотреть следующее дерево поиска:

Двоичное дерево поиска
Рис. 2. Двоичное дерево поиска

В таком дереве достаточно просто найти элемент. Мы должны, начиная с корня, сравнивать ключ текущей вершины с искомым и, в зависимости от результата сравнения, двигаться в левое или правое поддерево. Для примера путь поиска ключа 8 будет выглядеть примерно так:

Поиск в дереве поиска
Рис. 3. Поиск в дереве поиска

Операции

Помимо операции поиска такие деревья должны поддерживать операцию вставки, которая сводится к поиску места для вставки и непосредственной вставки. Обычно именно эта операция усложняется для того, чтобы дерево было сбалансированным. Различные реализации этой операции мы рассмотрим в соответствующих разделах.

Кроме этого на деревьях поиска часто рассматривают операцию взятия интервала (range scan) — выбрать все элементы, чьи ключи находятся в интервале \((a, b)\), то есть \(\{u \in T \colon a < k(u) < b\}\). Здесь стоит отметить, что не смотря на то, что стоимость отдельного поиска составляет \(O(h)\), учётная стоимость перехода от элемента к элементу при взятии интервала составляет \(O(1)\)(?).

Также бывает необходимо обойти все вершины и применить к каждой определённую функцию. Большинство алгоритмов обхода являются рекурсивными и можно выделить следующие фазы обхода конкретной вершины:

  • N — применение функции к текущей вершине;
  • L — рекурсивное рассмотрение левого поддерева;
  • R — рекурсивное рассмотрение правого поддерева;

Собственно чаще всего применяется обход слева направо, то есть фаза L должна проходить раньше R. А вот фазу N можно разместить в одной из трёх позиций, получая следующие обходы (пример обхода на дереве с рисунка 2):

  • NLR — прямой обход (pre-order): 10, 6, 1, 7, 6, 8, 18, 13, 21;
  • LNR — центрированный обход (in-order): 1, 6, 6, 7, 8, 10, 13, 18, 21;
  • LRN — обратный обход (post-order): 1, 6, 8, 7, 6, 13, 21, 18, 10;

Прямой обход подходит для получения разницы Merkle tree, обратный обход позволяет упростить сериализацию и десериализацию деревьев поиска, когда при десериализации для каждого элемента применяется простая операция вставки. А центрированный обход похож на выбор интервала \((-\infty; +\infty)\).

Есть ещё одна операция, которая часто оказывается востребованной для дерева поиска: удаление элемента. Эту операцию можно разделить на 2 подвида: удаление по ключу или удаление по локатору. Собственно от этого зависит то, как искать элемент, а сама операция удаления сводится к объединению поддеревьев сыновей удаляемого элемента:

Объединение деревьев поиска (до)
Рис. 5. Объединение деревьев поиска (до)
Объединение деревьев поиска (после)
Рис. 6. Объединение деревьев поиска (после)

Деревья с поддержкой баланса

Как было замечено выше, сложность операций поиска и вставки напрямую зависит от высоты дерева, поэтому хорошо бы поддерживать дерево сбалансированным. Для этого существует несколько подходов. Целый класс алгоритмов поддержки баланса построенны на хранении дополнительной информации в вершинах: АВЛ-, красно-чёрные, АА-деревья, дуча и другие. Собственно как и для левацких куч, где была необходимость в хранении дополнительной информации, так и для некоторых алгоритмов этого класса дополнительную информацию можно заменить случайностью. Помимо этого есть класс алгоритмов, поддерживающих баланс за счёт своего строения: B-деревья и, отчасти, splay-деревья.

Повороты

Для рассматриваемых в данной статье алгоритмов необходима базовая операция поворота дерева. Визуально поворот выглядит следующим образом:

Поворот вершины
Рис. 7. Поворот вершины

Перестроение графа из состояния 1 в состояние 2 называется правым поворотом, обратное — левым. Очевидно, что при таких поворотах свойства дерева поиска сохраняются:

\[ \begin{gathered} \forall u \in \alpha \implies u \leqslant x, \\ \forall u \in \beta \implies x \leqslant u \leqslant y, \\ \forall u \in \gamma \implies y \leqslant u, \end{gathered} \]
то есть свойства сортирующего дерева инвариантны относительно поворотов. При этом после правого поворота высота левого поддерева уменьшилась как минимум на единицу, а высота правого поддерева увеличилась как минимум на единицу. То есть применяя подобные повороты можно балансировать высоты правого и левого поддеревьев.

Вооружившись операциями поворотов, мы можем перейти к рассмотрению АВЛ-деревьев.

АВЛ-дерево

АВЛ-дерево было изобретено советскими математиками Адельсон-Вельским и Ландисом в 1962 году и названо по первым буквам их фамилий. Это дерево является классическим примером дерева поиска с поддержкой баланса. Иногда, под термином самобалансирующееся двоичное дерево поиска (self-balancing binary search tree) понимается именно АВЛ-дерево. Например, в книге Н. Вирта раздел, посвящённый деревьям поиска, рассматривает именно АВЛ-деревья.

В классической реализации АВЛ-дерева в каждой вершине \(u\) хранится высота дерева с корнем в этой вершине \(h(u)\). Будем считать, что высота пустого дерева равно нулю, а высота непустого дерева на единицу больше максимума высот его правого и левого поддеревьев.

\[ h(\varnothing) = 0 \quad\text{и}\quad h(u) = 1 + \max(h(u_\ell), h(u_r)). \]

В качестве инварианта, который мы будем поддерживать, возьмём следующее правило:

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

Этот инвариант может нарушиться после вставки нового элемента. Давайте добавим к дереву, изображённому на рисунке 2 новый элемент: 9. Для начала мы должны выполнить поиск ключа 9 в имеющемся дереве. Этот поиск приведёт нас к вершине 8, которая является листом. Таким образом новый элемент мы должны вставить как правый сын этой вершины, оставив левого сына пустым:

Вставка нового элемента в дерево поиска
Рис. 8. Вставка нового элемента в дерево поиска

Давайте рассмотрим высоты вершин для полученного дерева.

Высоты вершин до и после вставки элемента
Рис. 9. Высоты вершин до и после вставки элемента

Здесь стоит заметить, что после вставки высота может измениться только у вершин, располагающихся на пути поиска места вставки, поэтому необходимо сохранить этот путь в стек и после вставки вернуться по нему, обновляя высоты вершин. При этом в некоторых вершинах может нарушиться правило, выбранное нами в качестве инварианта. В нашем примере это вершина с ключом 6:

Нарушение инварианта АВЛ-дерева
Рис. 10. Нарушение инварианта АВЛ-дерева

Для восстановления баланса необходимо выполнить левый поворот вокруг этой вершины, после чего получим следующее дерево высот:

Поворот проблемной вершины
Рис. 11. Поворот проблемной вершины

В итоге мы получаем дерево, в каждой вершине которого выполняется инвариант АВЛ-дерева:

АВЛ-дерево после вставки и балансировки
Рис. 12. АВЛ-дерево после вставки и балансировки

Стоит отметить, что инвариант АВЛ-дерева не эквивалентен правилу сбалансированности (расстояния от листьев до корня равны с точностью до единицы), так, например, для любого натурального \(n\) можно построить АВЛ-дерево, в котором будут два листа, расстояния которых до корня будут отличаться на \(n\) (?).

Проблема АВЛ-дерева заключается в том, что в каждой вершине необходимо хранить высоту её поддерева, что при большом количестве данных является существенными затратами. На самом деле размер дополнительной памяти можно сократить до 2 бит на вершину, храня в них лишь 3 состояния:

  • 00 — высота левого и правого поддерева равны;
  • 01 — высота правого поддерева больше высоты левого поддерева на 1;
  • 10 — высота левого поддерева больше высоты правого поддерева на 1;

Этих вариантов хватит для описания инварианта АВЛ-дерева, а также позволит понять — нарушен ли инвариант при возврате по стеку поиска.

Хранение деревьев для минимизации чтений с диска

Во вступлении было упомянуто о том, что деревья поиска позволяют также минимизировать чтения с диска. Для этого необходимо хранить деревья определённым образом. Разобьём всё дерево на поддеревья размером в блок чтения с диска, например 1 Кб. Пусть в узлах хранятся данные размером в 8 байт, тогда дерево размером 1 Кб будет содержать \(1024 / 8 = 128\) узлов, \(64\) из которых являются листьями. Под каждым листом мы можем «подцепить» два других дерева в качестве сыновей. Получится дерево деревьев:

Хранение дерева как фрактала
Рис. 13. Хранение дерева как фрактала

При таком подходе 1 Гб данных можно уложить в 3 слоя таких деревьев. Таким образом для поиска элемента будет достаточно будет считать по одному дереву с каждого слоя, то есть совершить 3 чтения. При этом можно хранить деревья из 3 слоёв локально, так что при увеличении количества данных можно будет рассматривать это дерево как структуру, состоящую из гигабайтных деревьев.

Такой подход к хранению структур данных называется кеш-независимым (cache-oblivious) и позволяет не только уменьшить количество чтений с диска, но и оптимизировать работу с кеш-линиями процессора.

Вопросы

  1. ^ Докажите учётную стоимость операции получения следующего элемента при взятии интервала. Какова будет сложность обхода всего дерева?
  2. ^ Докажите этот факт. А также докажите, что высота дерева всё равно будет ограничена \(O(\log n)\).
  3. Прочитайте статью Randomized binary search trees1 и покажите достоинства и недостатки АВЛ и рандомизированных деревьев.

Задания

  1. Реализуйте АВЛ-дерево с хранением в каждом элементе лишь одного из трёх состояний: высоты поддеревьев равны, высота левого поддерева больше, высота правого поддерева больше.
  2. Реализуйте операцию удаления элемента из АВЛ-дерева по ключу.
  3. * Реализуйте хранение АВЛ-дерева в виде фрактальной структуры.

Дополнительное чтение

  1. Вирт, Никлаус. Алгоритмы и структуры данных. Новая версия для Оберона. Перевод Ткачев, Ф. В., М.: ДМК Пресс, 2016.

  1. Martinez, Conrado; Roura, Salvador. “Randomized binary search trees.” Journal of the ACM (ACM Press). vol. 45 iss. 2, 1998, pp. 288–323. http://akira.ruc.dk/~keld/teaching/algoritmedesign_f08/Artikler/03/Martinez97.pdf ↩︎