Что такое сбалансированное дерево
Перейти к содержимому

Что такое сбалансированное дерево

  • автор:

Балансировка — Алгоритмы на деревьях

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

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

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

Сбалансированные деревья

Идеальная сбалансированность — это свойство дерева, при котором все его уровни, иногда кроме последнего, полностью заполнены.

Для сравнения рассмотрим два бинарных дерева поиска, которые будут представлять собой одну последовательность элементов — 1,2,3,4,5,6. Из этой последовательности можно построить несколько деревьев, например:

В дереве (б) каждый из уровней, кроме левой ветки узла 1, заполнены. Значит, дерево (б) — идеально сбалансированное дерево. Что нельзя сказать о дереве (а).

Дерево (а) и дерево (б) можно отнести к бинарным деревьям поиска. Но для худшего случая — поиска в дереве элемента №6 в дереве (а) — требуется выполнить шесть операций перехода между вершинами, а в случае (б) — только три.

Дерево с максимально возможной высотой (а) называется разбалансированным или вырожденным деревом. Оно не отличается от двусвязного списка, значит, теряет свое основное преимущество — скорость поиска.

Для разбалансированных деревьев скорость составляет

. А для идеально сбалансированного дерева (б) поиск будет завершен за число шагов, которые не превышают высоту дерева или за

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

Чтобы вернуть дерево в сбалансированный вид, его перестраивают после каждой манипуляции с составом узлов. Рассмотрим пример с добавлением элемента №7 в наше дерево. Это можно сделать несколькими способами:

В случае (б) дерево вышло из состояния идеальной сбалансированности, так как оба нижних уровня не заполнены полностью. В таком случае поиск элемента №7 будет выполнен за четыре операции.

В случае (а) элементы были перераспределены, чтобы сохранить сбалансированное состояние. В таком случае поиск элемента №7 будет выполнен всего за три операции.

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

Ресурсы вычислительных машин не безграничны. Чтобы снизить нагрузку на них и одновременно с этим максимально сохранить преимущества идеально сбалансированного дерева, придумали новые виды деревьев. Среди них особенно выделяются АВЛ-деревья и красно-черные деревья, с которыми мы познакомимся подробнее.

АВЛ-деревья

Этот вид деревьев представили в 1962 году двое советских ученых: Адельсон-Вельский Г.М. и Ландис Е.М. Именно по сокращению от их фамилий АВЛ-деревья и получили такое название.

АВЛ-деревья отличаются от идеально сбалансированных. АВЛ-дерево считается сбалансированным, если для каждого узла дерева высота его правого и левого поддеревьев отличаются не более чем на единицу. Если модификация структуры узлов приводит к нарушению сбалансированности дерева, то необходимо выполнить его балансировку.

Поиск в АВЛ-дереве выполняется аналогично работе с бинарным деревом поиска. При этом благодаря поддержке возможности ребалансировки при вставки и удалении узлов в АВЛ-деревьях есть особенности реализации.

В качестве индикатора наличия разбалансированности в поддереве на узел выносят показатель баланса, который принимает значения от -1 до +1. Их значения:

  • –1 — в правом поддереве больше высота
  • 0 — поддеревья равной высоты
  • +1 — высота больше в левом поддереве

В итоге код нашего узла принимает следующий вид:

class AvlTreeNode  constructor(value, parent)  this.left = null; //ссылка на левый дочерний узел this.right = null; //ссылка на правый дочерний this.balanceFactor = 0; //показатель сбалансированности this.parent = parent; //ссылка на родителя this.value = value; //полезная нагрузка > >
class AvlTreeNode  public AvlTreeNode left = null; // ссылка на левый дочерний узел public AvlTreeNode right = null; // ссылка на правый дочерний public int balanceFactor = 0; // показатель сбалансированности public AvlTreeNode parent; // ссылка на родителя public Object value; // полезная нагрузка AvlTreeNode(Object value, AvlTreeNode parent)  this.parent = parent; this.value = value; > >
class AvlTreeNode: def __init__(self, value, parent=None): self.left = None # ссылка на левый дочерний узел self.right = None # ссылка на правый дочерний узел self.balance_factor = 0 # показатель сбалансированности self.parent = parent # ссылка на родителя self.value = value # полезная нагрузка
php class AvlTreeNode  public $left = null; // ссылка на левый дочерний узел public $right = null; // ссылка на правый дочерний public $balanceFactor = 0; // показатель сбалансированности public $parent; // ссылка на родителя public $value; // полезная нагрузка public function __construct($value, $parent)  $this->parent = $parent; $this->value = $value; > >

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

Далее мы подробно поговорим об операциях добавления и удаления узлов в АВЛ-деревьях.

Модификация структуры узлов

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

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

Вращение вправо выполняется за три шага:

  1. Текущий корень поддерева (D) заменяется на левый дочерний узел (B)
  2. Предыдущий корень (D) становится правым дочерним узлом для (B)
  3. Предыдущее правое поддерево узла (B) становится левым поддеревом для (D)

Вращение влево выполняется аналогично:

  1. Текущий корень поддерева (D) заменяется на правый дочерний узел ©
  2. Предыдущий корень (D) становится левым дочерним узлом для ©
  3. Предыдущее левое поддерево узла © становится правым поддеревом для (D)

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

Всего выделяется четыре варианта развития событий:

  • Левое поддерево левой дочерней вершины
  • Левое поддерево правой дочерней вершины
  • Правое поддерево левой дочерней вершины
  • Правое поддерево правой дочерней вершины

Рассмотрим пример, который описывает первый случай — вставку в левое поддерево левой дочерней вершины. Изображенные треугольники представляют собой сбалансированные АВЛ-поддеревья. Они могут содержать большое количество вершин. У вершины В дерево не сбалансировано, поскольку поддерево А1 в вершине А на два уровня выше, чем поддерево В2:

Чтобы сбалансировать дерево, необходимо совершить правое вращение — заменить вершину В вершиной А и сделать поддерево А2 левым поддеревом вершины В. После такого преобразования наше поддерево примет следующий вид:

Четвертый сценарий будет выглядеть аналогично кроме замены способа вращения на левое.

Для второго и третьего сценариев необходимо выполнить вращение дважды:

Удаление узлов также осуществляется при помощи механизмов вращения. При возврате во время рекурсивного спуска осуществляется вычисление balanceFactor. Если он отклоняется от допустимых значений, то выполняется ребалансировка аналогично добавлению узла.

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

Красно-черные деревья

Красно-черные деревья — одни из наиболее активно используемых на практике самобалансирующихся деревьев. Они так называются из-за наличия на узле дополнительного поля, в котором размещается цвет узла. В качестве стандартных цветов используют обычно красные и черные узлы, а сам цвет узла используется во время балансировки.

Так как красно-черные деревья самобалансирующиеся, то среднее и худшее время поиска тоже составляют

. А операции вставки и удаления узла могут потребовать поворот поддерева.

Для красно-черного дерева наш код узла примет следующий вид:

class RBTreeNode  constructor(value, parent)  this.left = null; //ссылка на левый дочерний узел this.right = null; //ссылка на правый дочерний this.isRed = false; //цвет узла. Если не красный, то считаем что узел черный this.parent = parent; //ссылка на родителя this.value = value; //полезная нагрузка > >
class RBTreeNode  public RBTreeNode left = null; // ссылка на левый дочерний узел public RBTreeNode right = null; // ссылка на правый дочерний public boolean isRed = false; // Цвет узла // Если узел не красный, то считаем что он черный public RBTreeNode parent; // ссылка на родителя public Object value; // полезная нагрузка RBTreeNode(Object value, RBTreeNode parent)  this.parent = parent; this.value = value; > >
class RBTreeNode: def __init__(self, value, parent=None): self.left = None # ссылка на левый дочерний узел self.right = None # ссылка на правый дочерний узел self.is_red = False # цвет узла. Если не красный, то считаем что узел черный self.parent = parent # ссылка на родителя self.value = value # полезная нагрузка
php class RBTreeNode  public $left = null; // ссылка на левый дочерний узел public $right = null; // ссылка на правый дочерний public $isRed = false; // Цвет узла // Если узел не красный, то считаем что он черный public $parent; // ссылка на родителя public $value; // полезная нагрузка public function __construct($value, $parent)  $this->parent = $parent; $this->value = $value; > >

В отличие от других видов деревьев в листовых узлах красно-черных деревьев не хранят полезную нагрузку. А цвет листовых узлов без данных всегда считается черным. Такая особенность позволяет считать ссылку на null валидным узлом. Эта особенность позволит сэкономить память. А само дерево принимает следующий вид:

Помимо особенностей работы с листовыми узлами к свойствам красно-черного так же относят:

  1. Корень красно-черного дерева черный
  2. Две красные вершины не могут идти подряд ни на одном пути. Оба потомка каждого красного узла — черные
  3. Для каждой вершины, в каждом исходящем из нее пути, одинаковое число черных вершин

Иногда при работе с узлами красно-черного дерева используют черную высоту — количество черных вершин на исходящих из нее путях, не включая саму исходную вершину.

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

Сбалансированность этих деревьев хуже, чем у АВЛ-деревьев. При этом затраты на поддержание состояния сбалансированности и потребление памяти меньше, а операцию поиска можно выполнять одновременно с выполнением перестроения дерева.

Благодаря этим преимуществам сфера применения красно-черных деревьев существенно шире. Так, например, в стандартной библиотеке шаблонов языка C++ STL и TreeMap в Java применяются именно красно-черные деревья.

Сбалансированное бинарное дерево из отсортированного массива

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

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

Сбалансированное оно, видимо, потому что в таком дереве в среднем требуется наименьшее количество операций для поиска.

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

�� Веду телеграм-канал с еженедельными разборами задач для собеседований.

Каким образом реализовать алгоритм?

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

Этот способ не слишком эффективен — обход дерева требует O(log N) операций, чтобы вставить каждый узел потребуется O(n * log N) времени.

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

Алгоритм получился примерно такой:

  • выбрать средний элемент массива в качестве корня
  • начинать создавать левое поддерево из левой части массива
  • начинать создавать правое поддерево из правой части массива
  • повторить рекурсивно, пока не закончатся элементы в массиве

Реализация получилась довольно простой. Единственное на что нужно обратить внимание — смещение на единицу при выборе границ частей массива.

Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.

АВЛ-дерево

АВЛ-дерево (англ. AVL-Tree) — сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

Высота дерева

АВЛ-дерево с [math]n[/math] ключами имеет высоту [math]h = O(\log n)[/math] .

Высоту поддерева с корнем [math]x[/math] будем обозначать как [math]h(x)[/math] , высоту поддерева [math]T[/math] — как [math]h(T)[/math] .

Пусть [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math] , тогда [math]m_h = F_ — 1[/math] , где [math]F_h — h[/math] -ое число Фибоначчи.

Если [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math] . Тогда как легко видеть, [math]m_ = m_ + m_h + 1[/math] . Равенство [math]m_h = F_ — 1[/math] докажем по индукции.

База индукции [math]m_1 = F_3 — 1[/math] — верно, [math]m_1 = 1, F_3 = 2[/math] .

Допустим [math]m_h = F_ — 1[/math] — верно.

Тогда [math]m_ = m_h + m_ + 1 = F_ — 1 + F_ — 1 + 1 = F_ — 1[/math] .

[math]F_h = \Omega(\varphi^h)[/math] , [math]\varphi = \dfrac< \sqrt+1>[/math] . То есть

[math]n \geqslant \varphi^[/math]

Логарифмируя по основанию [math]\varphi[/math] , получаем

[math]\log_n \geqslant h[/math]

Балансировка

Балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев [math]|h(L) — h(R)| = 2[/math] , изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева [math]|h(L) — h(R)| \leqslant 1[/math] , иначе ничего не меняет. Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева [math]diff[i] = h(L) — h(R)[/math]

Для балансировки вершины используются один из 4 типов вращений:

[math]diff[a] = -2[/math] и [math]diff[b] = -1[/math]

[math]diff[a] = -2[/math] и [math]diff[b] = 0[/math] .

[math]diff[a] = 0[/math] и [math]diff[b] = 0[/math]

[math]diff[a] = -1[/math] и [math]diff[b] = 1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = -1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 0[/math] .

[math]diff[a] = 0[/math] , [math]diff[b] = -1[/math] и [math]diff[c] = 0[/math]

[math]diff[a] = 1[/math] , [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

[math]diff[a] = 0[/math] , [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

Малый левый поворот:

function rotateLeft(Node a): Node b = a.right a.right = b.left b.left = a корректировка высоты a корректировка высоты b

Большой левый поворот пишется проще:

function bigRotateLeft(Node a): rotateRight(a.right) rotateLeft(a)

Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению. В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на [math]1[/math] и не может увеличиться.

Все вращения, очевидно, требуют [math]O(1)[/math] операций.

Операции

Добавление вершины

Пусть нам надо добавить ключ [math]t[/math] . Будем спускаться по дереву, как при поиске ключа [math]t[/math] . Если мы стоим в вершине [math]a[/math] и нам надо идти в поддерево, которого нет, то делаем ключ [math]t[/math] листом, а вершину [math]a[/math] его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то [math]diff[i][/math] увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным [math]2[/math] или [math]-2[/math] , то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем [math] O(h) [/math] вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет [math] O(\log) [/math] операций.

Удаление вершины

Для простоты опишем рекурсивный алгоритм удаления. Если вершина — лист, то удалим её, иначе найдём самую близкую по значению вершину [math]a[/math] , переместим её на место удаляемой вершины и удалим вершину [math]a[/math] . От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то [math]diff[i][/math] уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным [math]2[/math] или [math]-2[/math] , следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, [math] O(h) [/math] операций. Таким образом, требуемое количество действий — [math] O(\log) [/math] .

Поиск вершины, минимум/максимум в дереве, etc.

Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в наивной реализации дерева поиска.

Слияние двух AVL-деревьев

Дано два дерева [math]T_1[/math] и [math]T_2[/math] , все ключи в [math]T_1[/math] меньше ключей в [math]T_2[/math] , [math]h(T_1) \leqslant h(T_2)[/math] .

В дереве [math]T_1[/math] удаляем самую правую вершину, назовём её [math]b[/math] . Высота дерева [math]T_1[/math] может уменьшиться на единицу. В дереве [math]T_2[/math] идём от корня всегда в левое поддерево и, когда высота этого поддерева [math]P[/math] будет равна высоте дерева [math]T_1[/math] , делаем новое дерево [math]S[/math] , корнем [math]S[/math] будет вершина [math]b[/math] , левым поддеревом будет дерево [math]T_1[/math] , а правым дерево [math]P[/math] . Теперь в дереве [math]T_2[/math] у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево [math]S[/math] и запускаем балансировку. Таким образом, дерево [math]T_2[/math] будет результатом слияния двух АВЛ-деревьев.

Дерево [math]T_1[/math] и [math]T_2[/math] до слияния

Avl u3.jpg

Дерево [math]T_2[/math] после слияния

Avl u4.jpg

Алгоритм разделения AVL-дерева на два

Алгоритм первый

Пусть у нас есть дерево [math]T[/math] . Мы должны разбить его на два дерева [math]T_[/math] и [math]T_[/math] такие, что [math]T_ \leqslant x[/math] и [math]x \lt T_[/math] .

Предположим, что корень нашего дерева [math]\leqslant x[/math] , в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево [math]T_[/math] . Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи [math]\leqslant x[/math] ). Если же корень оказался [math]\gt x[/math] , то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.

Пусть мы пришли в поддерево [math]S[/math] , корень которого [math]\leqslant x[/math] . В таком случае этот корень со своим левым поддеревом должен отойти в дерево [math]T_[/math] . Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево [math]S[/math] , удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL’ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево [math]S[/math] ). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины [math]S[/math] и запускаем балансировку. Обозначим полученное дерево за [math]T'[/math] . Теперь нам нужно объединить его с уже построенным ранее [math]T_[/math] (оно может быть пустым, если мы первый раз нашли такое дерево [math]S[/math] ). Для этого мы ищем в дереве [math]T_[/math] самое правое поддерево [math]P[/math] высоты, равной высоте [math]T'[/math] (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево [math]K[/math] , сливая [math]P[/math] и [math]T'[/math] (очевидно, все ключи в [math]T_[/math] меньше ключей в [math]T'[/math] , поэтому мы можем это сделать). Теперь в дереве [math]T_[/math] у отца вершины, в которой мы остановились при поиске дерева [math]P[/math] , правым поддеревом делаем дерево [math]K[/math] и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева [math]S[/math] (по ссылке, которую мы ранее запомнили) и обработать его.

Если мы пришли в поддерево [math]Q[/math] , корень которого [math]\gt x[/math] , совершаем аналогичные действия: делаем NULL’ами ссылки на корень [math]Q[/math] , запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины [math]Q[/math] и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее [math]T_[/math] аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево [math]T_[/math] .

Рассмотрим пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево [math]T_[/math] . [math]x = 76[/math] .

Рис. 1. Разделение АВЛ-дерева на два.

Корень дерева [math]\leqslant x[/math] , поэтому он со всем выделенным поддеревом должен отойти в дерево [math]T_[/math] . По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево [math]T'[/math] (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был [math]\leqslant x[/math] , [math]T'[/math] становится [math]T_[/math] . Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень [math]\gt x[/math] . Следовательно, строим из него и его правого поддерева [math]T_[/math] и спускаемся в левое поддерево. Снова корень [math]\leqslant x[/math] . Строим новое [math]T'[/math] и объединяем его с уже существующим [math]T_[/math] (рис. 3).

Рис. 2. Создание T’.

Рис. 3. Объединение T’ и T1.

Далее действуем по алгоритму и в итоге получаем (рис. 4):

Рис. 4. АВЛ-деревья после разделения.

Данный алгоритм имеет сложность [math]O(\log^ n)[/math] .

Алгоритм второй

Рассмотрим решение, которое имеет сложность [math]O(\log)[/math] .

Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья [math]T_[/math] и [math]T_[/math] , передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево [math]T_[/math] придет вершина [math]75[/math] с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением [math]70[/math] и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.

Пусть мы пришли в поддерево [math]S[/math] с корнем [math]\leqslant x[/math] . Тогда сольем его с уже построенным на тот момент [math]T_[/math] ( [math]T_[/math] пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, [math]S \leqslant T_[/math] и [math]h(T_) \leqslant h(S)[/math] ). Но так как обычная процедура слияния сливает два АВЛ-дерева, а [math]S[/math] не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве [math]S[/math] нашли самое правое поддерево [math]K[/math] , высота которого равна высоте [math]T_[/math] . Тогда сделаем новое дерево [math]T'[/math] , корнем которого будет вершина [math]S[/math] (без нее это дерево является сбалансированным), правым поддеревом — [math]T_[/math] , левым — [math]K[/math] . И подвесим [math]T'[/math] на то место, где мы остановились при поиске [math]K[/math] . Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, [math]\gt x[/math] , все аналогично.

Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла [math]77[/math] . Ключ больше [math]x[/math] , поэтому эта вершина станет деревом [math]T_[/math] и передастся наверх. Теперь мы поднялись в узел [math]75[/math] . Он со своим левым поддеревом станет деревом [math]T_[/math] и мы снова поднимемся наверх в узел [math]70[/math] . Он со своим левым поддеревом снова должен отойти в дерево [math]T_[/math] , и так как теперь дерево [math]T_[/math] уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5)

После мы поднимемся в вершину с ключом [math]80[/math] . Она с правым поддеревом отойдет в дерево [math]T_[/math] (рис. 6).

И на последней итерации мы поднимемся в корень дерева с ключом [math]50[/math] , он с левым поддеревом отойдет в дерево [math]T_[/math] , после чего алгоритм завершится.

Пусть поддеревьев с ключами [math]\leqslant x[/math] оказалось больше, чем поддеревьев с ключами [math]\gt x[/math] . Докажем для них логарифмическую асимптотику. Дерево на последнем уровне имеет высоту [math]H_[/math] (она может быть не равна [math]1[/math] , если мы придём в [math]x[/math] ). Его мы передаем наверх и вставляем в поддерево высотой [math]H_[/math] . [math]H_ \leqslant H_[/math] , так как разница высот поддеревьев у любой вершины не больше [math]1[/math] , и мы при переходе от [math]H_[/math] к [math]H_[/math] поднимаемся как минимум на одну вершину вверх. Слияние этих поддеревьев мы выполним за [math]H_ — H_[/math] , получим в итоге дерево высоты не большей, чем [math]H_[/math] . Его мы передадим наверх, поэтому в следующий раз слияние будет выполнено за [math]H_ — H_[/math] и так далее. Таким образом мы получим [math](H — H_) + (H_ — H_) + (H_ — H_) + \cdots + (H_ — H_) = H — H_ = O(\log)[/math] .

Итоговая асимптотика алгоритма — [math]O(\log)[/math] .

АВЛ-дерево с O(1) бит в каждом узле

Идея

В обычной реализации АВЛ-дерева в каждом узле мы хранили высоту этого узла. Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на [math]1[/math] , то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать, какое поддерево больше, или равны ли они, назовём фактор баланса. Таким образом в каждом узле будет храниться [math]1[/math] — если высота правого поддерева выше левого, [math]0[/math] — если высоты равны, и [math]-1[/math] — если правое поддерево выше левого.

Операции

Операция добавления
Пусть нам надо добавить ключ [math]t[/math] . Будем спускаться по дереву, как при поиске ключа [math]t[/math] . Если мы стоим в вершине [math]a[/math] и нам надо идти в поддерево, которого нет, то делаем ключ [math]t[/math] листом, а вершину [math]a[/math] его корнем. Пересчитываем баланс данного узла [math]a[/math] . Если он оказался [math]0[/math] , то высота поддерева с корнем в этой вершине не изменилась и пересчет балансов останавливается. Дальше начинаем подниматься вверх по дереву, исправляя балансы попутных узлов. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то баланс увеличивается на единицу, если из правого, то уменьшается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота поддерева изменилась, и подъём продолжается. Если баланс вершины [math]a[/math] , в которую мы собираемся идти из ее левого поддерева, равен [math]1[/math] , то делается поворот для этой вершины [math]a[/math] . Аналогично делаем поворот, если баланс вершины [math]a[/math] , в которую мы идем из ее правого поддерева, равен [math]-1[/math] . Если в результате изменения узла, фактор баланса стал равен нулю, то останавливаемся, иначе продолжаем подъём.

Операция удаления
Если вершина — лист, то просто удалим её, иначе найдём ближайшую по значению вершину [math]a[/math] , поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то фактор баланса уменьшается на единицу, если из правого, то увеличивается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота поддерева не изменилась, и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс вершины [math]a[/math] , в которую мы собираемся идти из ее левого поддерева, равен [math]-1[/math] , то делается поворот для этой вершины [math]a[/math] . Аналогично делаем поворот, если баланс вершины [math]a[/math] , в которую мы идем из ее правого поддерева, равен [math]1[/math] . Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.

Балансировка

Опишем операции балансировки, а именно малый левый поворот, большой левый поворот и случаи их возникновения. Балансировка нам нужна для операций добавления и удаления узла. Для исправления факторов баланса, достаточно знать факторы баланса двух(в случае большого поворота — трех) вершин перед поворотом, и исправить значения этих же вершин после поворота. Обозначим фактор баланса вершины [math]i[/math] как [math]balance[i][/math] . Операции поворота делаются на том шаге, когда мы находимся в правом сыне вершины [math]a[/math] , если мы производим операцию добавления, и в левом сыне, если мы производим операцию удаления. Вычисления производим заранее, чтобы не допустить значения [math]2[/math] или [math]-2[/math] в вершине [math]a[/math] . На каждой иллюстрации изображен один случай высот поддеревьев. Нетрудно убедиться, что в остальных случаях всё тоже будет корректно.

1 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = -1[/math]

2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 0[/math]

1 вариант: [math]balance[a] = 0[/math] и [math]balance[b] = 0[/math]

2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 1[/math]

1 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = 1[/math]

2 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = -1[/math]

3 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = 0[/math]

1 вариант: [math]balance[a] = 0[/math] , [math]balance[b] = -1[/math] и [math]balance[c] = 0[/math]

2 вариант: [math]balance[a] = 1[/math] , [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]

3 вариант: [math]balance[a] = 0[/math] , [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]

Примеры

Ниже приведены примеры добавления и удаления вершины с подписанными изменениями факторов баланса каждой вершины.

Сбалансированные двоичные деревья поиска: реализация на Julia

Иллюстрация из работы Г.М. Адельсон-Вельского и Е.М. Ландиса 1962 года

Деревья поиска — это структуры данных для упорядоченного хранения и простого поиска элементов. Широко применяются двоичные деревья поиска, в которых у каждого узла есть только два потомка. В этой статье рассмотрим два метода организации двоичных деревьев поиска: алгоритм Адельсон-Вельского и Ландиса (АВЛ-деревья) и ослабленные АВЛ-деревья (WAVL-деревья).

Начнём с определений. Двоичное дерево состоит из узлов, каждый узел хранит запись в виде пар ключ-значение (либо, в простом случае, только значений) и имеет не более двух потомков. Узлы-потомки различаются на правый и левый, причём выполняется условие на упорядоченность ключей: ключ левого потомка не больше, а правого — не меньше, чем ключ родительского узла. Дополнительно в узлах может храниться (и обычно хранится) служебная информация — например, ссылка на родительский узел или другие данные. Специальными случаями являются корневой узел, с которого происходит вход в дерево, и пустой узел, который не хранит никакой информации. Узлы, у которых оба потомка пустые, называются листьями дерева. Узел со всеми потомками образует поддерево. Таким образом, каждый узел либо является корнем какого-то поддерева, либо листом.

Это определение позволяет построить простейшую структуру для хранения узлов и самого дерева. Будем считать, что пустой узел имеет специальное значение nothing типа Nothing . Тогда в узле достаточно хранить ссылки на правого и левого потомка и на родителя. Структура для хранения дерева содержит только ссылку на корневой узел.

# K - тип ключей # V - тип хранимых значений mutable struct BSTNode key::K value::V left::Union> right::Union> parent::BSTNode end mutable struct BST root::BSTNode end

В этом случае возникает вопрос, каким образом представить пустое дерево. Воспользуемся для этого подходом из книги «Алгоритмы: построение и анализ» и вставим в качестве точки входа в дерево не корень, а фиктивный узел, который будет своим собственным родителем. Для создания такого узла нужно добавить в описание структуры BSTNode конструкторы:

mutable struct BSTNode key::K value::V left::Union> right::Union> parent::BSTNode # пустой конструктор function BSTNode() where node = new() node.parent = node node.left = node.right = nothing return node end # конструктор с парой ключ-значение function BSTNode(key, value) where node = new() node.parent = node node.left = node.right = nothing node.key, node.value = key, value return node end end BSTNode() = BSTNode() # Теперь структуру можно сделать неизменяемой! struct BST entry::BSTNode BST() where = new(BSTNode()) end BST() = BST() Base.isempty(bst::BST) = bst.entry.left == nothing

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

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

# Перегрузка функции Base.getindex() позволяет в дальнейшем # обращаться к элементу через синтаксис tree[key] function Base.getindex(bst::BST, key) where key = convert(K, key) node = bst.entry.left while node != nothing key == node.key && return node.value node = (key < node.key ? node.left : node.right) end throw(KeyError(key)) end

Поиск элемента по ключу, очевидно, занимает время O(h), где h — высота дерева, т.е. максимальное расстояние от корня до листа. Как легко посчитать, двоичное дерево высоты h может как максимум содержать 2 h+1 -1 узлов, если оно плотно заполнено, т.е. все узлы, кроме, может быть, самого крайнего слоя, имеют обоих потомков. К тому же понятно, что любую наперёд заданную последовательность ключей можно привести к такому плотному дереву. Это даёт весьма оптимистичную асимптотику поиска элемента в дереве при его оптимальном построении за время O(log2N), где N — число элементов.

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

# Перегрузка функции Base.setindex!() позволяет в дальнейшем # добавлять или менять элементы через синтаксис tree[key] = value function Base.setindex!(bst::BST, val::SV, key::SK) where key, value = convert(K, key), convert(V, val) parent = bst.entry.left # отдельный случай - вставка в пустое дерево if parent == nothing newnode.parent = bst.entry bst.entry.left = bst.entry.right = newnode return val end key_found = false while !key_found if key < parent.key if parent.left == nothing parent.left = BSTNode(key, value) parent.left.parent = parent key_found = true else parent = parent.left end elseif key > parent.key if parent.right == nothing parent.right = BSTNode(key, value) newnode.parent = parent key_found = true else parent = parent.right end else key_found = true parent.value = value end end return val end

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

Вывод: дерево поиска при построении нужно балансировать, т.е. выравнивать высоту правого и левого поддерева у каждого узла. К балансировке есть несколько подходов. Простейший — задать некоторое число операций вставки или удаления, после которого будет производиться перебалансировка дерева. В таком случае дерево будет перед балансировкой будет в довольно "запущенном" состоянии, из-за чего балансировка будет занимать время порядка O(N) в худшем случае, зато последующие операции до некоторого порога вставок/удалений будут выполняться за логарифмическое время. Другой же вариант — строить алгоритмы вставки и удаления сразу так, чтобы дерево постоянно оставалось сбалансированным, что даёт для любой операции гарантированную временную сложность O(log2N).

В связи с тем, что есть алгоритмы, в которых дереву позволяют "разбалтываться", но после этого довольно долго операции можно проводить за логарифмическое время, прежде чем придётся долго приводить дерево обратно в сбалансированное состояние, различают гарантированное и амортизированное время вставки/удаления элемента. Для некоторых реализаций операций с двоичными деревьями поиска сложность вставки и удаления O(log2N) является гарантированной, для некоторых — амортизированной, с ухудшением до O(N).

Алгоритм Адельсон-Вельского и Ландиса (АВЛ)

Первая реализация самобалансирующегося двоичного дерева поиска была предложена в 1962 году Адельсоном-Вельским и Ландисом. В современной литературе по начальным буквам фамилий эта структура называется АВЛ-деревья. Структура описывается следующими свойствами:

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

Из этих свойств следует, что высота всего дерева составляет O(log2N), где N — число хранимых в дереве записей, а значит, поиск записи происходит за логарифмическое время. Чтобы условие АВЛ-сбалансированности сохранялось после каждой вставки, каждая вставка сопровождается операцией балансировки. Для эффективного осуществления этой операции в каждом узле нужно хранить служебную информацию. Для простоты, пусть там просто хранится высота узла.

mutable struct AVLNode # надеемся, что высота дерева не будет больше 255 # (не больше 10^38 записей) height::UInt8 key::K value::V left::Union right::Union parent::AVLNode # пустой конструктор function AVLNode() where node = new() node.height = 1 node.parent = node node.left = node.right = nothing return node end # конструктор с парой ключ-значение function AVLNode(key::SK, value::SV) where node = new() node.height = 1 node.parent = node node.left = node.right = nothing node.key, node.value = key, value return node end end avlheight(node::Union) = node == nothing ? 0 : Int(node.height)
Вставка записи

Базовая вставка делается по стандартному алгоритму — спускаемся по дереву вниз, ищем, куда можно вставить новый узел и вставляем. Напишем обёртки для получения и замены дочерних узлов с использованием индексов -1 и 1 вместо левого и правого:

function child(root::AVLNode, side::Signed) if side == -1 root.left elseif side == 1 root.right else throw(ArgumentError("Expecting side=-1 to get the left child or side=1 to get the right child")) end end function insert_child!(root::AVLNode, newnode::Union, side::Signed) where newnode == nothing || (newnode.parent = root) if side == -1 root.left = newnode elseif side == 1 root.right = newnode else throw(ArgumentError("Expecting side=-1 for inserting node to the left or side=1 for inserting to the right")) end end

Далее, идём вверх по дереву и ищем нарушения условий 2 и 3. Далее рассмотрим варианты, которые могут появиться (на рисунках зелёным обозначен узел, поменявший высоту, обрабатываемый узел — его родитель).

Случай 0
После вставки высота узла стала такой же, как у сестринского, и на 1 меньше (старой) высоты родительского узла.

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

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

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

fucntion promote!(nd::AVLNode, by::Integer=1) nd.height += by end fucntion demote!(nd::AVLNode, by::Integer=1) nd.height -= by end

Случай 2

После вставки разница высот с сестринским поддеревом стала 2, причём "вытолкнуло" вверх левое поддерево:

Проблема лечится операцией, называемой "простой поворот", преобразующей дерево следующим образом:

На простой поворот требуется 6 изменений указателей.

Обратите внимание, что в проекции на горизонтальную ось порядок вершин n, p и деревьев T1T3 до и после поворота остаётся одним и тем же. Это — выполнение условия упорядоченности. Как видно, после выполнения поворота выше по дереву балансировка уже не требуется.

# pivot оказывается в конце на самом верху function rotate!(pivot::AVLNode, dir::Signed) dir in (-1, 1) || throw(ArgumentError("Unknown rotation direction")) p = pivot.parent g = p.parent p.height = avlheight(child(pivot, dir)) + 1 pivot.height = p.height + 1 # "перецепляем" pivot к g pivot.parent = g g.left === p && (g.left = pivot) g.right === p && (g.right = pivot) c = child(pivot, dir) # перецепляем c к p insert_child!(p, c, -dir) # перецепляем p к pivot insert_child!(pivot, p, dir) pivot end

Случай 3
После вставки разница высот с сестринским поддеревом стала 2, причём "вытолкнуло" вверх правое поддерево:

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

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

Как видно, после двойного поворота дальнейшей балансировки выше по дереву также не требуется.

# pivot оказывается в конце на самом верху funсtion double_rotate!(pivot::AVLNode, dir::Signed) dir in (-1, 1) || throw(ArgumentError("Unknown rotation direction")) n = pivot.parent p = n.parent g = p.parent pivot.height = n.height n.height = p.height = pivot.height - 1 # "перецепляем" pivot к g pivot.parent = g g.left === p && (g.left = pivot) g.right === p && (g.right = pivot) t2, t3 = child(pivot, -dir), child(pivot, dir) # перецепляем n к pivot и t2 к n insert_child!(n, t2, dir) insert_child!(pivot, n, -dir) # перецепляем p к pivot и t3 к p insert_child!(p, t3, -dir) insert_child!(pivot, p, dir) pivot end

Итак, при вставке записи в АВЛ-дерево нужно O(log2N) изменений информации о высоте узлов и не более двух операций поворота. Объединим всё в одну функцию вставки. От базовой вставки она будет отличаться только тем, что после вставки нового узла вызывается функция fix_insertion!() , которая проходит от только что вставленного узла к корню, проверяет и при необходимости исправляет балансировку.

function Base.setindex!(avlt::AVLTree, val, key) where key, value = convert(K, key), convert(V, val) parent = avlt.entry.left # отдельный случай - вставка в пустое дерево if parent == nothing newnode = AVLNode(key, value) newnode.parent = avlt.entry avlt.entry.left = avlt.entry.right = newnode return val end key_found = false while !key_found key_found = key == parent.key if key_found parent.value = value else side = (key > parent.key) * 2 - 1 # true == 1, false == 0 next = child(parent, side) if next == nothing newnode = AVLNode(key, value) insert_child!(parent, newnode, side) fix_insertion!(newnode) key_found = true else parent = next end end end return val end

Функция fix_insertion!() проверяет разницу высот двух дочерних узлов, начиная с родительского узла от вставленного. Если она равна 1 — мы находимся в случае 1, нужно поднять высоту узла и пройти выше. Если она ноль — дерево сбалансировано. Если она равна 2 — это случай 2 или 3, нужно применить соответствующий поворот, и дерево приходит к сбалансированному состоянию.

# если правое поддерево выше - дисбаланс положительный, # если левое - отрицательный imbalance(node::AVLNode) = avlheight(node.right) - avlheight(node.left) function fix_insertion!(start::AVLNode) node = start.parent skew = imbalance(node) # у фиктивного входного узла дисбаланс 0 - т.е. попадание в него можно отдельно не проверять while abs(skew) == 1 node.height += 1 node = node.parent skew = imbalance(node) end @assert abs(skew) == 2 || skew == 0 if skew != 0 # повернуть надо в сторону более низкого дерева, # т.е. противоположно дисбалансу dir = -skew ÷ 2 n = child(node, -dir) prev_skew = imbalance(n) @assert abs(prev_skew) == 1 if prev_skew == dir double_rotate!(child(n, dir), dir) else rotate!(n, dir) end end end
Удаление записи

Удаление несколько сложнее вставки.

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

  1. Если удаляемая запись в листе — то запись просто удаляется, тут всё просто.
  2. Если удаляемая запись в узле, у которого только один потомок — то этот потомок вместе со всем своим поддеревом ставится на место удалённого узла.
  3. Если потомков два — то либо в левом поддереве ищется максимальный элемент, либо в правом минимальный, извлекается из дерева (по свойству дерева поиска узел с максимальным элементом гарантированно не имеет правого потомка, а с минимальным — левого, так что это удаление делается просто) и ставится на место удаляемой записи.

Но после этого может нарушиться баланс дерева, поэтому от родителя удалённого узла нужно пройтись вверх, восстанавливая его. Заметим, что в самом начале гарантированно один из потомков рассматриваемого родителя уменьшил высоту на 1. С учётом этого нужно рассмотреть варианты (красным показаны узлы, поменявшие высоту, обрабатываемый узел — родительский от красного):

Случай 1
Нулевой дисбаланс. Значит, до удаления он был 1 по модулю, и теперь дочерние узлы на 2 ниже материнского.

Нужно опустить родительский узел на 1 и продолжить движение вверх.

Случай 2
Дисбаланс 1 по модулю.

АВЛ-условие выполнено, можно остановиться.

Случай 3
Дисбаланс 2 по модулю, сестринский узел к опустившемуся имеет ненулевой дисбаланс.

Восстанавливаем баланс простым (если T1 ниже, чем T2) или двойным (в обратном случае) поворотом, как делали при вставке. Высота поддерева при этом уменьшается, т.е. может возникнуть нарушение выше по дереву.

Случай 4
Дисбаланс 2 по модулю, сестринский узел имеет нулевой дисбаланс.

Простой поворот восстанавливает условие балансировки, высота поддерева при этом не меняется — останавливаем движение наверх.

Код для удаления ключа

function next_node(node::AVLNode) next = node.right if next == nothing p = node.parent next = p.parent while (next !== p) && (next.key < p.key) p, next = next, next.parent end return (next === p ? nothing : next) else while next.left != nothing next = next.left end return next end end function Base.delete!(avlt::AVLTree, key) where key = convert(K, key) candidate = avlt.entry.left dir = 0 while candidate.key != key dir = 2 * (key > candidate.key) - 1 candidate = child(candidate, dir) candidate == nothing && return end val = candidate.value for side in (-1, 1) if child(candidate, side) == nothing p, s = candidate.parent, child(candidate, -side) if p === p.parent insert_child!(p, s, 1) insert_child!(p, s, -1) else insert_child!(p, s, dir) fix_deletion!(p) end return end end swap = next_node(candidate) cp, sp, sr = candidate.parent, swap.parent, swap.right swap.height = candidate.height insert_child!(swap, candidate.left, -1) for side in (-1, 1) child(cp, side) === candidate && insert_child!(cp, swap, side) end if sp === candidate fix_deletion!(swap) else insert_child!(swap, candidate.right, 1) insert_child!(sp, sr, -1) fix_deletion!(sp) end return end function fix_deletion!(start::AVLNode) node = start skew = imbalance(node) while (node !== node.parent) && (abs(skew) != 1) if skew != 0 @assert abs(skew) == 2 dir = -skew ÷ 2 n = child(node, -dir) prev_skew = imbalance(n) @assert abs(prev_skew) < 2 if prev_skew == dir node = double_rotate!(child(n, dir), dir) else node = rotate!(n, dir) prev_skew != 0 || break end else node.height -= 1 end node = node.parent skew = imbalance(node) end end

Взлёт и падение АВЛ-деревьев

Не очень приятное свойство классических АВЛ-деревьев состоит в сложности удаления записи: т.к. поворот может "сбросить" всё поддерево на уровень вниз, то в худшем случае удаление требует O(log2N) поворотов дерева — при каждом переходе на уровень вверх в fix_deletion!() .

Из-за этой не очень хорошей асимптотики АВЛ-деревья уступили место появившимся в 1970-х красно-чёрным деревьям, у которых более слабое условие балансировки — путь от корня до самого дальнего листа не более чем вдвое превышает путь от корня до самого ближнего листа. Из-за этого высота красно-чёрных деревьев составляет в худшем случае 2log2N против 1,44log2N у АВЛ-деревьев, зато удаление записи требует не более трёх простых поворотов. Таким образом, поиск и вставка за счёт более высокой высоты дерева потенциально проигрывают в производительности, зато есть потенциальный выигрыш, если вставки часто перемежаются удалениями.

АВЛ наносят ответный удар

Получается, что "идеальный" алгоритм построения двоичных деревьев поиска должен гарантировать небольшую высоту (на уровне классического АВЛ-дерева) и константное число поворотов как при добавлении, так и при удалении записи. Такого пока не придумано, но в 2015 году была опубликована работа, где предложена структура, улучшающая свойства как АВЛ, так и красно-чёрных деревьев. Идея лежит ближе к АВЛ деревьям, но условие баланса ослаблено, чтобы позволить более эффективное удаление записей. Свойства структуры, названной "слабым АВЛ-деревом" (W(eak)AVL-деревом) формулируются таким образом:

  1. Упорядоченность: для любого узла ключ в вершине левого поддерева меньше, а в вершине правого поддерева — больше, чем ключ самого узла (если потомки не являются пустыми узлами).
  2. Возрастание ранга. Каждому узлу приписывается ранг. Ранг всех пустых узлов равен нулю, ранг листов — 1. Ранг родительского узла строго больше ранга дочернего.
  3. Слабая АВЛ-сбалансированность: ранг узла отличается от ранга дочерних узлов не более чем на 2.

Оказывается, что такая структура включает в себя свойства и классических АВЛ-деревьев, и красно-чёрных деревьев. В частности, если ввести условие, что оба дочерних узла не могут отличаться от родительского по рангу на 2, то получится обычное АВЛ дерево, а ранг будет точно совпадать с высотой поддерева.

Прелесть САВЛ-деревьев в том, что небольшое ослабление АВЛ-условия позволяет балансировать дерево при удалении записи не более чем двумя поворотами! Оценка на высоту дерева составляет h < min(1,44log2M, 2log2N), где N — число записей в дереве, M — число вставок, по сравнению с h < 2log2N для красно-чёрных деревьев. Более того, если САВЛ-дерево строится только вставками, то оно будет идентично классическому АВЛ дереву, полученному из той же последовательности ключей.

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

Структура хранения.

Можно оставить структуру обычного АВЛ-дерева, только "высота" должна пониматься как "ранг". Для понятности, сделаем отдельную структуру:

mutable struct WAVLNode rank::UInt8 key::K value::V left::Union> right::Union> parent::WAVLNode # пустой конструктор function WAVLNode() where node = new() node.rank = 1 node.parent = node node.left = node.right = nothing return node end # конструктор с парой ключ-значение function WAVLNode(key, value) where key, value = convert(K, key), convert(V, value) node = new() node.rank = 1 node.parent = node node.left = node.right = nothing node.key, node.value = key, value return node end end struct WAVLTree entry::WAVLNode WAVLTree() where = new(WAVLNode()) end function child(root::WAVLNode, side::Signed) if side == -1 root.left elseif side == 1 root.right else throw(ArgumentError("Expecting side=-1 to get the left child or side=1 to get the right child")) end end function Base.getindex(avlt::WAVLTree, key) where key = convert(K, key) node = avlt.entry.left while node != nothing key == node.key && return node.value node = (key < node.key ? node.left : node.right) end throw(KeyError(key)) end
Вставка записи

Алгоритм практически такой же, как и в обычном АВЛ-дереве. Едиственное отличие: если в базовом варианте дисбаланс 1 после вставки гарантированно означал, что родительский узел нужно поднять — то в ослабленном варианте нужно проверить, разница в рангах у родителя с самым высоким потомком 0 (тогда нужно поднять) или 1 (тогда делать ничего не надо). Для этого немного изменим функцию imbalance() , чтобы она возвращала и то, и другое.

wavlrank(node::Union) = node == nothing ? 0 : Int(node.rank) function imbalance(node::WAVLNode) rr, lr = wavlrank(node.right), wavlrank(node.left) skew = rr - lr diff = node.rank - max(rr, lr) skew, diff end

Код поворотов немного меняется, чтобы не писать разные функции для поворота при вставке и удалении. При вставке, учитывая конфигурации, которые там могут возникать, он работает так же, как в обычном АВЛ-дереве, для удаления чуть-чуть иначе.

Оставшийся код для вставки

# pivot оказывается в конце на самом верху function rotate!(pivot::AVLNode, dir::Signed) dir in (-1, 1) || throw(ArgumentError("Unknown rotation direction")) p = pivot.parent g = p.parent p.height = avlheight(child(pivot, dir)) + 1 pivot.height = p.height + 1 # "перецепляем" pivot к g pivot.parent = g g.left === p && (g.left = pivot) g.right === p && (g.right = pivot) c = child(pivot, dir) # перецепляем c к p insert_child!(p, c, -dir) # перецепляем p к pivot insert_child!(pivot, p, dir) pivot end # pivot оказывается в конце на самом верху function double_rotate!(pivot::AVLNode, dir::Signed) dir in (-1, 1) || throw(ArgumentError("Unknown rotation direction")) n = pivot.parent p = n.parent g = p.parent pivot.height = n.height n.height = p.height = pivot.height - 1 # "перецепляем" pivot к g pivot.parent = g g.left === p && (g.left = pivot) g.right === p && (g.right = pivot) t2, t3 = child(pivot, -dir), child(pivot, dir) # перецепляем n к pivot и t2 к n insert_child!(n, t2, dir) insert_child!(pivot, n, -dir) # перецепляем p к pivot и t3 к p insert_child!(p, t3, -dir) insert_child!(pivot, p, dir) pivot end imbalance(node::AVLNode) = avlheight(node.right) - avlheight(node.left) function fix_insertion!(start::AVLNode) node = start.parent skew = imbalance(node) while abs(skew) == 1 node.height += 1 node = node.parent skew = imbalance(node) end @assert abs(skew) == 2 || skew == 0 if skew != 0 dir = -skew ÷ 2 n = child(node, -dir) prev_skew = imbalance(n) @assert abs(prev_skew) == 1 if prev_skew == dir double_rotate!(child(n, dir), dir) else rotate!(n, dir) end end end function Base.setindex!(avlt::AVLTree, val, key) where key, value = convert(K, key), convert(V, val) parent = avlt.entry.left # отдельный случай - вставка в пустое дерево if parent == nothing newnode = AVLNode(key, value) newnode.parent = avlt.entry avlt.entry.left = avlt.entry.right = newnode return val end key_found = false while !key_found key_found = key == parent.key if key_found parent.value = value else side = (key > parent.key) * 2 - 1 next = child(parent, side) if next == nothing newnode = AVLNode(key, value) insert_child!(parent, newnode, side) fix_insertion!(newnode) key_found = true else parent = next end end end return val end
Удаление записи

Поиск узла для удаления, поиск следующего и замена — полностью идентичны обычным АВЛ-деревьям. Для балансировки при обратном проходе рассматриваются следующие случаи.

Случай 0
Ни одно из условий баланса не нарушено, т.е.:

  1. Дисбаланс 1, самое высокое поддерево на 1 ниже родителя
  2. Дисбаланс 0, оба поддерева на 2 ниже родителя, при этом поддеревья не пустые.
    Балансировка на этом завершается.

Случай 1
Имеем лист с рангом 2 (дисбаланс 0, поддеревья на 2 ниже и пустые).
Присваиваем узлу ранг 1 и переходим выше.

Случай 2
Дисбаланс 1, разница с максимальным поддеревом 2.

Уменьшаем у узла ранг на 1, переходим выше.

Случай 3
Дисбаланс 2 (разница с максимальным поддеревом автоматически 1, т.к. иначе слабое АВЛ условие было бы нарушено ещё до удаления), у более высокого потомка оба поддерева рангом на 2 ниже его.

Спускаем на ранг ниже и сам узел, и более высокого потомка. Переходим выше.

Случай 4

Лечится простым поворотом.

Обратите внимание, что за счёт ослабленного АВЛ условия поворот можно сделать так, что всё поддерево не меняет высоту, т.е. выше по дереву балансировка не требуется.

Единственная тонкость — если деревья T1 и T2 оба пустые, то p становится листом с рангом 2, что лечится присваиванием p в этом случае ранга 1.

Случай 5

Лечится двойным поворотом.

Аналогично, высота поддерева не меняется, и балансировку можно на этом заканчивать.

Код для удаления записи

function next_node(node::WAVLNode) next = node.right if next == nothing p = node.parent next = p.parent while (next !== p) && (next.key < p.key) p, next = next, next.parent end return (next === p ? nothing : next) else while next.left != nothing next = next.left end return next end end function Base.delete!(avlt::WAVLTree, key) where key = convert(K, key) candidate = avlt.entry.left dir = 0 while candidate.key != key dir = 2 * (key > candidate.key) - 1 candidate = child(candidate, dir) candidate == nothing && return end val = candidate.value for side in (-1, 1) if child(candidate, side) == nothing p, s = candidate.parent, child(candidate, -side) if p === p.parent insert_child!(p, s, 1) insert_child!(p, s, -1) else insert_child!(p, s, dir) fix_deletion!(p) end return end end swap = next_node(candidate) cp, sp, sr = candidate.parent, swap.parent, swap.right swap.height = candidate.height insert_child!(swap, candidate.left, -1) for side in (-1, 1) child(cp, side) === candidate && insert_child!(cp, swap, side) end if sp === candidate fix_deletion!(swap) else insert_child!(swap, candidate.right, 1) insert_child!(sp, sr, -1) fix_deletion!(sp) end return end function fix_deletion!(start::WAVLNode) node = start skew, diff = imbalance(node) while (node !== node.parent) if skew == 0 if node.right == nothing node.rank = 1 else break end elseif abs(skew) == 1 if diff == 1 break else node.rank -= 1 end else dir = -skew ÷ 2 n = child(node, -dir) prev_skew, prev_diff = imbalance(n) if prev_diff == 2 @assert prev_skew == 0 n.rank -= 1 node.rank -= 1 elseif prev_skew == dir double_rotate!(child(n, dir), dir) break else rotate!(n, dir) break end end node = node.parent skew, diff = imbalance(node) end end

Проверим в сравнении со встроенными хэш-таблицами.

julia> const wavl = WAVLTree() julia> const avl = AVLTree() julia> const dd = Dict() julia> x = trues(1_000_000) # заполним числами и случайным образом удалим ~ половину julia> for i = 1:1_000_000; dd[i] = avl[i] = wavl[i] = i * i; end julia> for i=1:500_000 k = rand(1:1_000_000) x[k] = false delete!(avl, k) delete!(wavl, k) delete!(dd, k) end # запомнили, какие ключи не удалялись julia> const y = Int[] julia> for i in eachindex(x); if x[i] push!(y, i); end; end julia> @btime let s = 0.0; for idx in y; s += dd[idx]; end; s; end 57.626 ms (0 allocations: 0 bytes) 2.0238199367708794e17 julia> @btime let s = 0.0; for idx in y; s += wavl[idx]; end; s; end 57.796 ms (0 allocations: 0 bytes) 2.0238199367708794e17 julia> @btime let s = 0.0; for idx in y; s += avl[idx]; end; s; end 53.884 ms (0 allocations: 0 bytes) 2.0238199367708794e17

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

Применение деревьев поиска

И основной вопрос — зачем это нужно?
Простейший ответ — деревья поиска нужны, чтобы искать информацию. Но, на самом деле, не только.

На основе двоичных деревьев поиска можно реализовать различные абстрактные структуры данных.

Упорядоченное множество

Задача упорядоченного множества — хранить элементы так, чтобы к ним можно было доступаться в порядке возрастания или убывания. Также можно ввести операцию поиска n-го по величине элемента. Естественно, структуру данных рассматриваем как динамическую, т.е. кроме перечисления, мы хотим добавлять или удалять оттуда элементы.

Операция АВЛ дерево Сортированный массив
Перечислить все элементы O(N) O(N)
Вставка O(logN) O(N)
Удаление O(logN) O(N)
n-й элемент O(logN)* O(1)

* если в узлах хранить информацию о размере поддерева

Ассоциативный массив

Ассоциативный массив — абстрактная структура данных, для которой основными операциями являются "найти запись по ключу", "проверить наличие ключа в массиве", "добавить пару ключ-значение", "удалить запись". Во многих языках программирования, где структура включена в стандартную библиотеку, реализация сделана с помощью двоичных деревьев или хэш-таблиц. Языки семейства Лисп поддерживают ассоциативные списки. В конце концов, записи можно даже просто хранить в массиве в отсортированном порядке.

Операция АВЛ дерево хэш-таблица Список Сортированный массив
Поиск O(logN) O(1)* O(N) O(logN)
Вставка O(logN) O(1)* O(1) O(N)
Удаление O(logN) O(1)* O(N)** O(N)
Поиск ближайшего ключа O(logN) O(N) O(N) O(logN)

* амортизированная стоимость операции
** само удаление делается за O(1), но ключ ещё нужно найти.

Очередь с приоритетами

Это такая структура данных, где хранятся записи в виде пар "приоритет — данные". Извлекаются записи не в порядке поступления, а в порядке приоритета. Основные операции — посмотреть элемент с максимальным (или минимальным) приоритетом, удалить из очереди запись со старшим приоритетом, добавить запись, изменить приоритет записи. Часто такие очереди реализуются при помощи двоичной кучи.

Операция АВЛ дерево Двоичная куча Список Сортированный список/массив
Посмотреть максимум O(1)* O(1) O(N) O(1)
Удалить максимум O(logN) O(logN) O(N) O(1)**
Добавить запись O(logN) O(logN) O(1) O(N)
Изменить приоритет O(logN) O(logN) O(N) O(N)

* если добавить в структуру указатель на максимум
** если считать, что максимум находится в конце массива

Вывод

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

Ссылки

  1. "АВЛ-деревья" от nickme
  2. Rank-Balanced Trees by Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan // ACM Transactions on Algorithms | June 2015, Vol 11(4) pdf
  3. Goodrich M.T., Tamassia R. Algorithm Design and Applications
  • Julia
  • алгоритмы
  • авл-дерево
  • двоичные деревья поиска

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *