АВЛ-деревья
Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.
Понятие АВЛ-дерева
АВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла. Это значит, что для поиска нужного ключа в АВЛ-дереве можно использовать стандартный алгоритм. Для простоты дальнейшего изложения будем считать, что все ключи в дереве целочисленны и не повторяются.
Особенностью АВЛ-дерева является то, что оно является сбалансированным в следующем смысле: для любого узла дерева высота его правого поддерева отличается от высоты левого поддерева не более чем на единицу. Доказано, что этого свойства достаточно для того, чтобы высота дерева логарифмически зависела от числа его узлов: высота h АВЛ-дерева с n ключами лежит в диапазоне от log2(n + 1) до 1.44 log2(n + 2) − 0.328. А так как основные операции над двоичными деревьями поиска (поиск, вставка и удаление узлов) линейно зависят от его высоты, то получаем гарантированную логарифмическую зависимость времени работы этих алгоритмов от числа ключей, хранимых в дереве. Напомним, что рандомизированные деревья поиска обеспечивают сбалансированность только в вероятностном смысле: вероятность получения сильно несбалансированного дерева при больших n хотя и является пренебрежимо малой, но остается не равной нулю.
Структура узлов
Будем представлять узлы АВЛ-дерева следующей структурой:
Поле key хранит ключ узла, поле height — высоту поддерева с корнем в данном узле, поля left и right — указатели на левое и правое поддеревья. Простой конструктор создает новый узел (высоты 1) с заданным ключом k.
Традиционно, узлы АВЛ-дерева хранят не высоту, а разницу высот правого и левого поддеревьев (так называемый balance factor), которая может принимать только три значения -1, 0 и 1. Однако, заметим, что эта разница все равно хранится в переменной, размер которой равен минимум одному байту (если не придумывать каких-то хитрых схем «эффективной» упаковки таких величин). Вспомним, что высота h < 1.44 log2(n + 2), это значит, например, что при n=10 9 (один миллиард ключей, больше 10 гигабайт памяти под хранение узлов) высота дерева не превысит величины h=44, которая с успехом помещается в тот же один байт памяти, что и balance factor. Таким образом, хранение высот с одной стороны не увеличивает объем памяти, отводимой под узлы дерева, а с другой стороны существенно упрощает реализацию некоторых операций.
Определим три вспомогательные функции, связанные с высотой. Первая является оберткой для поля height, она может работать и с нулевыми указателями (с пустыми деревьями):
Вторая вычисляет balance factor заданного узла (и работает только с ненулевыми указателями):
Третья функция восстанавливает корректное значение поля height заданного узла (при условии, что значения этого поля в правом и левом дочерних узлах являются корректными):
Заметим, что все три функции являются нерекурсивными, т.е. время их работы есть величина О(1).
Балансировка узлов
В процессе добавления или удаления узлов в АВЛ-дереве возможно возникновение ситуации, когда balance factor некоторых узлов оказывается равными 2 или -2, т.е. возникает расбалансировка поддерева. Для выправления ситуации применяются хорошо нам известные повороты вокруг тех или иных узлов дерева. Напомню, что простой поворот вправо (влево) производит следующую трансформацию дерева:
Код, реализующий правый поворот, выглядит следующим образом (как обычно, каждая функция, изменяющая дерево, возвращает новый корень полученного дерева):
Левый поворот является симметричной копией правого:
Рассмотрим теперь ситуацию дисбаланса, когда высота правого поддерева узла p на 2 больше высоты левого поддерева (обратный случай является симметричным и реализуется аналогично). Пусть q — правый дочерний узел узла p, а s — левый дочерний узел узла q.
Анализ возможных случаев в рамках данной ситуации показывает, что для исправления расбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q больше высоты его правого поддерева: h(s)≤h(D).
Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.
Код, выполняющий балансировку, сводится к проверке условий и выполнению поворотов:
Описанные функции поворотов и балансировки также не содержат ни циклов, ни рекурсии, а значит выполняются за постоянное время, не зависящее от размера АВЛ-дерева.
Вставка ключей
Вставка нового ключа в АВЛ-дерево выполняется, по большому счету, так же, как это делается в простых деревьях поиска: спускаемся вниз по дереву, выбирая правое или левое направление движения в зависимости от результата сравнения ключа в текущем узле и вставляемого ключа. Единственное отличие заключается в том, что при возвращении из рекурсии (т.е. после того, как ключ вставлен либо в правое, либо в левое поддерево, и это дерево сбалансировано) выполняется балансировка текущего узла. Строго доказывается, что возникающий при такой вставке дисбаланс в любом узле по пути движения не превышает двух, а значит применение вышеописанной функции балансировки является корректным.
Чтобы проверить соответствие реализованного алгоритма вставки теоретическим оценкам для высоты АВЛ-деревьев, был проведен несложный вычислительный эксперимент. Генерировался массив из случайно расположенных чисел от 1 до 10000, далее эти числа последовательно вставлялись в изначально пустое АВЛ-дерево и измерялась высота дерева после каждой вставки. Полученные результаты были усреднены по 1000 расчетам. На следующем графике показана зависимость от n средней высоты (красная линия); минимальной высоты (зеленая линия); максимальной высоты (синяя линия). Кроме того, показаны верхняя и нижняя теоретические оценки.
Видно, что для случайных последовательностей ключей экспериментально найденные высоты попадают в теоретические границы даже с небольшим запасом. Нижняя граница достижима (по крайней мере в некоторых точках), если исходная последовательность ключей является упорядоченной по возрастанию.
Удаление ключей
С удалением узлов из АВЛ-дерева, к сожалению, все не так шоколадно, как с рандомизированными деревьями поиска. Способа, основанного на слиянии (join) двух деревьев, ни найти, ни придумать не удалось. 
Поэтому за основу был взят вариант, описываемый практически везде (и который обычно применяется и при удалении узлов из стандартного двоичного дерева поиска). Идея следующая: находим узел p с заданным ключом k (если не находим, то делать ничего не надо), в правом поддереве находим узел min с наименьшим ключом и заменяем удаляемый узел p на найденный узел min.
При реализации возникает несколько нюансов. Прежде всего, если у найденный узел p не имеет правого поддерева, то по свойству АВЛ-дерева слева у этого узла может быть только один единственный дочерний узел (дерево высоты 1), либо узел p вообще лист. В обоих этих случаях надо просто удалить узел p и вернуть в качестве результата указатель на левый дочерний узел узла p.
Пусть теперь правое поддерево у p есть. Находим минимальный ключ в этом поддереве. По свойству двоичного дерева поиска этот ключ находится в конце левой ветки, начиная от корня дерева. Применяем рекурсивную функцию:
Еще одна служебная функция у нас будет заниматься удалением минимального элемента из заданного дерева. Опять же, по свойству АВЛ-дерева у минимального элемента справа либо подвешен единственный узел, либо там пусто. В обоих случаях надо просто вернуть указатель на правый узел и по пути назад (при возвращении из рекурсии) выполнить балансировку. Сам минимальный узел не удаляется, т.к. он нам еще пригодится.
Теперь все готово для реализации удаления ключа из АВЛ-дерева. Сначала находим нужный узел, выполняя те же действия, что и при вставке ключа:
Как только ключ k найден, переходим к плану Б: запоминаем корни q и r левого и правого поддеревьев узла p; удаляем узел p; если правое поддерево пустое, то возвращаем указатель на левое поддерево; если правое поддерево не пустое, то находим там минимальный элемент min, потом его извлекаем оттуда, слева к min подвешиваем q, справа — то, что получилось из r, возвращаем min после его балансировки.
При выходе из рекурсии не забываем выполнить балансировку:
Вот собственно и все! Поиск минимального узла и его извлечение, в принципе, можно реализовать в одной функции, при этом придется решать (не очень сложную) проблему с возвращением из функции пары указателей. Зато можно сэкономить на одном проходе по правому поддереву.
Очевидно, что операции вставки и удаления (а также более простая операция поиска) выполняются за время пропорциональное высоте дерева, т.к. в процессе выполнения этих операций производится спуск из корня к заданному узлу, и на каждом уровне выполняется некоторое фиксированное число действий. А в силу того, что АВЛ-дерево является сбалансированным, его высота зависит логарифмически от числа узлов. Таким образом, время выполнения всех трех базовых операций гарантированно логарифмически зависит от числа узлов дерева.
АВЛ-дерево
АВЛ-дерево (англ. AVL-Tree) — сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.
Содержание
Высота дерева
Высоту поддерева с корнем [math]x[/math] будем обозначать как [math]h(x)[/math] , высоту поддерева [math]T[/math] — как [math]h(T)[/math] .
Если [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math] . Тогда как легко видеть, [math]m_
База индукции [math]m_1 = F_3 — 1[/math] — верно, [math]m_1 = 1, F_3 = 2[/math] .
Допустим [math]m_h = F_
Тогда [math]m_
[math]F_h = \Omega(\varphi^h)[/math] , [math]\varphi = \dfrac< \sqrt<5>+1><2>[/math] . То есть
[math]n \geqslant \varphi^
Логарифмируя по основанию [math]\varphi[/math] , получаем
[math]\log_<\varphi>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]
Малый левый поворот:
Большой левый поворот пишется проще:
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению. В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на [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]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
Поиск вершины, минимум/максимум в дереве, 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] до слияния
Дерево [math]T_2[/math] после слияния
Алгоритм разделения AVL-дерева на два
Алгоритм первый
Пусть у нас есть дерево [math]T[/math] . Мы должны разбить его на два дерева [math]T_<1>[/math] и [math]T_<2>[/math] такие, что [math]T_ <1>\leqslant x[/math] и [math]x \lt T_<2>[/math] .
Предположим, что корень нашего дерева [math]\leqslant x[/math] , в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево [math]T_<1>[/math] . Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи [math]\leqslant x[/math] ). Если же корень оказался [math]\gt x[/math] , то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.
Пусть мы пришли в поддерево [math]S[/math] , корень которого [math]\leqslant x[/math] . В таком случае этот корень со своим левым поддеревом должен отойти в дерево [math]T_<1>[/math] . Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево [math]S[/math] , удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL’ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево [math]S[/math] ). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины [math]S[/math] и запускаем балансировку. Обозначим полученное дерево за [math]T'[/math] . Теперь нам нужно объединить его с уже построенным ранее [math]T_<1>[/math] (оно может быть пустым, если мы первый раз нашли такое дерево [math]S[/math] ). Для этого мы ищем в дереве [math]T_<1>[/math] самое правое поддерево [math]P[/math] высоты, равной высоте [math]T'[/math] (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево [math]K[/math] , сливая [math]P[/math] и [math]T'[/math] (очевидно, все ключи в [math]T_<1>[/math] меньше ключей в [math]T'[/math] , поэтому мы можем это сделать). Теперь в дереве [math]T_<1>[/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_<2>[/math] аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево [math]T_<2>[/math] .
Рассмотрим пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево [math]T_<1>[/math] . [math]x = 76[/math] .
Корень дерева [math]\leqslant x[/math] , поэтому он со всем выделенным поддеревом должен отойти в дерево [math]T_<1>[/math] . По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево [math]T'[/math] (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был [math]\leqslant x[/math] , [math]T'[/math] становится [math]T_<1>[/math] . Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень [math]\gt x[/math] . Следовательно, строим из него и его правого поддерева [math]T_<2>[/math] и спускаемся в левое поддерево. Снова корень [math]\leqslant x[/math] . Строим новое [math]T'[/math] и объединяем его с уже существующим [math]T_<1>[/math] (рис. 3).
Далее действуем по алгоритму и в итоге получаем (рис. 4):
Данный алгоритм имеет сложность [math]O(\log^ <2>n)[/math] .
Алгоритм второй
Рассмотрим решение, которое имеет сложность [math]O(\log
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья [math]T_<1>[/math] и [math]T_<2>[/math] , передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево [math]T_<1>[/math] придет вершина [math]75[/math] с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением [math]70[/math] и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.
Пусть мы пришли в поддерево [math]S[/math] с корнем [math]\leqslant x[/math] . Тогда сольем его с уже построенным на тот момент [math]T_<1>[/math] ( [math]T_<1>[/math] пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, [math]S \leqslant T_<1>[/math] и [math]h(T_<1>) \leqslant h(S)[/math] ). Но так как обычная процедура слияния сливает два АВЛ-дерева, а [math]S[/math] не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве [math]S[/math] нашли самое правое поддерево [math]K[/math] , высота которого равна высоте [math]T_<1>[/math] . Тогда сделаем новое дерево [math]T'[/math] , корнем которого будет вершина [math]S[/math] (без нее это дерево является сбалансированным), правым поддеревом — [math]T_<1>[/math] , левым — [math]K[/math] . И подвесим [math]T'[/math] на то место, где мы остановились при поиске [math]K[/math] . Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, [math]\gt x[/math] , все аналогично.
Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла [math]77[/math] . Ключ больше [math]x[/math] , поэтому эта вершина станет деревом [math]T_<2>[/math] и передастся наверх. Теперь мы поднялись в узел [math]75[/math] . Он со своим левым поддеревом станет деревом [math]T_<1>[/math] и мы снова поднимемся наверх в узел [math]70[/math] . Он со своим левым поддеревом снова должен отойти в дерево [math]T_<1>[/math] , и так как теперь дерево [math]T_<1>[/math] уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5)
После мы поднимемся в вершину с ключом [math]80[/math] . Она с правым поддеревом отойдет в дерево [math]T_<2>[/math] (рис. 6).
И на последней итерации мы поднимемся в корень дерева с ключом [math]50[/math] , он с левым поддеревом отойдет в дерево [math]T_<1>[/math] , после чего алгоритм завершится.
Пусть поддеревьев с ключами [math]\leqslant x[/math] оказалось больше, чем поддеревьев с ключами [math]\gt x[/math] . Докажем для них логарифмическую асимптотику. Дерево на последнем уровне имеет высоту [math]H_
Итоговая асимптотика алгоритма — [math]O(\log
АВЛ-дерево с 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]
Примеры
Ниже приведены примеры добавления и удаления вершины с подписанными изменениями факторов баланса каждой вершины.
19. Сбалансированные деревья (общее понятие). Виды деревьев.
В программировании используют достаточно много видов деревьев:
N-арное дерево — это дерево, в котором каждая вершина имеет не более чем N детей.
2-3 дерево — сбалансированное дерево поиска, такое, что каждый узел может иметь два или три сына и глубина всех листьев одинакова.
А еще В-деревья, деревья цифрового поиска, нагруженные деревья, patricia-деревья, синтаксические деревья и другие.
Но все-таки чаще всего используется бинарное дерево поиска, рассмотренное нами на предыдущем занятии. Но есть одно но…
Время выполнения базовых операций в дереве поиска линейно зависит от его высоты. Но из одного и того же набора ключей можно построить разные деревья поиска:
В приведенном примере на рисунке оба дерева построены из одного
и того же набора ключей, но высота первого дерева больше, поэтому время выполнения операций над ним будет больше. Например, при поиске узла с ключом 6 в первом случае требуется просмотреть все шесть узлов, а во втором только три узла: 3->5->6.
Второе дерево лучше сбалансировано, чем первое. Чем больше узлов в дереве, тем более очевидно преимущество дерева поиска над обычным двоичным деревом при условии, что дерево поиска хорошо сбалансировано.
Как построить дерево поиска минимальной высоты?
Если набор ключей известен заранее, то его надо упорядочить. Корнем поддерева становится узел с ключом, значение которого – медиана этого набора. Для упорядоченного набора, содержащего нечетное количество ключей, – это ключ, находящийся ровно в середине набора. Для набора 1,2,3,4,5,6, который содержит четное количество ключей, в качестве медианы может быть выбран ключ как со значением 3, так и со значением 4.
Для определенности выберем 3. Узел с этим ключом будет корнем дерева.
Далее, ключи, меньшие 3, попадут в левое поддерево, а ключи, большие 3, попадут в правое поддерево. Для построения левого и правого поддеревьев проделываем ту же процедуру на соответствующих наборах ключей. И так до тех пор, пока все ключи не будут включены в дерево.
Дерево, изображенное на рисунке выше справа является идеально сбалансированным, то есть, для каждого его узла количество узлов в левом и правом поддеревьях различается не более, чем на 1. Такое дерево можно построить для любого набора ключей. Достаточно заметить, что при выборе медианы на каждом шагу при построении дерева набор ключей разбивается на две части, и количество ключей в них может различаться не более, чем на 1.
Но полный набор ключей не всегда известен заранее.
Если ключи поступают по очереди, то построение дерева поиска будет зависеть от порядка их поступления. Если, например, ключи будут поступать в порядке 1,2,3,4,5,6, то получится дерево, изображенное на рисунке слева. Высота такого дерева максимальна для этого набора ключей, следовательно, и время выполнения операций над ним также будет максимальным. Поэтому при добавлении очередного узла, возможно, дерево понадобится перестраивать, чтобы уменьшить его высоту, сохраняя тот же набор узлов.
Идеальную балансировку поддерживать сложно. Если при добавлении очередного узла количество узлов в левом и правом поддеревьях какого-либо узла дерева станет различаться более, чем на 1, то дерево не будет являться идеально сбалансированным, и его надо будет перестраивать, чтобы восстановить свойства идеально сбалансированного дерева поиска. Поэтому обычно требования к сбалансированности дерева менее строгие.
Рассмотрим три основных вида сбалансированных деревьев поиска:
⦁ АВЛ-деревья,
⦁ красно-черные деревья и
⦁ самоперестраивающиеся деревья (splay-деревья).
Для АВЛ-деревьев сбалансированность определяется разностью высот правого и левого поддеревьев любого узла. Если эта разность по модулю не превышает 1, то дерево считается сбалансированным. Данное условие проверяется после каждого добавления или удаления узла, и определен минимальный набор операций перестройки дерева, который приводит к восстановлению свойства сбалансированности, если оно оказалось нарушено.
В красно-черных деревьях каждый узел имеет дополнительное свойство – цвет, красный или черный. На дерево наложены ограничения по расположению и количеству узлов в зависимости от цвета, и определен набор операций перестройки дерева в случае нарушения этих ограничений после добавления или удаления узла. Если АВЛ-деревья накладывают достаточно строгие условия на сбалансированность, и при добавлении узлов дерево достаточно часто приходится перестраивать, то в красно-черном дереве у каждого узла высоты левого и правого поддеревьев могут отличаться не более, чем в два раза.
И, наконец, третий вид рассматриваемых сбалансированных деревьев поиска – самоперестраивающиеся деревья. В отличие от двух предыдущих видов, у этих деревьев нет никаких ограничений на расположение узлов, а сбалансированность в среднем достигается за счет того, что каждый раз перед выполнением операции над узлом этот узел перемещается в корень дерева. Но есть вероятность того, что дерево в определенный момент может оказаться не сбалансированным.
2. АВЛ-деревья.
АВЛ-деревом называется такое дерево поиска, в котором для любого его узла высоты левого и правого поддеревьев отличаются не более, чем на 1. Эта структура данных разработана советскими учеными Адельсон-Вельским Георгием Максимовичем и Ландисом Евгением Михайловичем в 1962 году. Аббревиатура АВЛ соответствует первым буквам фамилий этих ученых. Первоначально АВЛ-деревья были придуманы для организации перебора в шахматных программах. Советская шахматная программа «Каисса» стала первым официальным чемпионом мира в 1974 году.
В каждом узле АВЛ-дерева, помимо ключа, данных и указателей на левое и правое поддеревья (левого и правого сыновей), хранится показатель баланса – разность высот правого и левого поддеревьев. Ниже приведен пример АВЛ-дерева. Таким образом, получается, что в АВЛ-дереве показатель баланса balance для каждого узла, включая корень, по модулю не превосходит 1. На рисунке ниже справа приведен пример дерева, которое не является АВЛ-деревом, поскольку в одном из узлов баланс нарушен, т.е. |balance|>1. Здесь и далее для АВЛ-деревьев будем указывать в узле значение показателя баланса.
Все операции над АВЛ-деревом очень похожи на операции с бинарным деревом поиска, но каждая операция требует еще и последующей балансировки дерева.
Но анализ возможных случаев показывает, что для исправления разбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q меньше высоты его правого поддерева: h(s)≤h(D).
Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.
3. Красно-черные деревья.
АВЛ-деревья исторически были первым примером использования сбалансированных деревьев поиска. В настоящее время более популярны красно-черные деревья (КЧ-деревья). Изобретателем красно-черного дерева считается немецкий ученый Рудольф Байер. КЧ-деревья – это двоичные деревья поиска, каждый узел которых хранит дополнительное поле color, обозначающее цвет: красный или черный, и для которых выполнены приведенные ниже свойства.
Будем считать, что если left или right равны NULL, то это «указатели» на фиктивные листья. Таким образом, все узлы – внутренние (нелистовые).
Свойства КЧ-деревьев:
1. каждый узел либо красный, либо черный;
2. каждый лист (фиктивный) – черный;
3. если узел красный, то оба его сына – черные;
4. все пути, идущие от корня к любому фиктивному листу, содержат одинаковое количество черных узлов;
5. корень – черный.
Определение: Черной высотой узла называется количество черных узлов на пути от этого узла к узлу, у которого оба сына – фиктивные листья.
Сам узел не включается в это число. Например, у дерева, приведенного на рисунке ниже, черная высота корня равна 2.
Определение: Черная высота дерева – черная высота его корня.
4. Самоперестраивающиеся деревья (splay trees).
Самоперестраивающееся дерево – это двоичное дерево поиска, которое, в отличие от предыдущих двух видов деревьев не содержит дополнительных служебных полей в структуре данных (баланс, цвет и т.п.). Оно позволяет находить быстрее те данные, которые использовались недавно. Самоперестраивающееся дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
Идея самоперестраивающихся деревьев основана на принципе перемещения найденного узла в корень дерева. После выполнения этой операции двоичное дерево перестраивается, оставаясь при этом деревом поиска, так, что:
⦁ если узел с ключом k есть в дереве, то он становится корнем;
⦁ если узла с ключом k нет в дереве, то корнем становится его предшественник или последователь.
Идея перемещения найденного узла в корень основана на предположении, что если тот же самый элемент потребуется в ближайшее время, он будет найден быстрее.
5. Сравнение АВЛ, красно-черных и самоперестраивающихся деревьев (splay trees).
В общем случае сравнение трех рассмотренных типов деревьев провести затруднительно, поскольку для разных задач и разных наборов данных лучший тип дерева может быть разным.
По сложности реализации самые простые – АВЛ-дерево, самые сложные – КЧ-деревья, поскольку приходится рассматривать много нетривиальных случаев при вставке и удалении узла. В теории операция удаления в КЧ-дереве эффективнее, в связи с чем они больше распространены.
Самоперестраивающиеся деревья существенно отличаются от АВЛ- и КЧ-деревьев потому что не накладывают никаких ограничений на структуру дерева. Операция поиска в дереве модифицирует само дерево, поэтому в случае обращения к разным узлам самоперестраивающееся дерево может работать медленнее. К тому же, в процессе работы дерево может оказаться полностью разбалансированным. Но доказано, что если вероятности обращения к узлам фиксированы, то самоперестраивающееся дерево будет работать асимптотически не медленнее двух других рассмотренных видов деревьев. Отсутствие дополнительных полей дает преимущество по памяти.
Различные виды сбалансированных деревьев поиска используются, в частности, в системном программном обеспечении, например, в ядрах операционных систем.
В каком случае какой вид деревьев лучше всего использовать.
Если входные данные полностью рандомизированы, то наилучшим вариантом оказываются деревья поиска общего вида – несбалансированные. Если входные данные в основном рандомизированные, но периодически встречаются упорядоченные наборы, то стоит выбрать КЧ-деревья. Если при вставке преобладают упорядоченные данные, то АВЛ-деревья оказываются лучше в случае, когда дальнейший доступ к элементам рандомизирован, а самоперестраивающиеся деревья – когда дальнейшие доступ последователен или кластеризован.
Итоги занятия.
В лесу из деревьев, даже если они виртуальные, действительно можно заблудиться. Помните, что подобные алгоритмы необходимы только в тех случаях, когда быстродействие программы вследствие огромного количества выполняемых ей операций по обработке данных является просто жизненно необходимым (конечно, для жизни самой программы). В этом случае смело бросайтесь в изучение соответствующей литературы и поиск готовых решений с последующей их оптимизацией под вашу задачу.
А на следующем занятии мы поймем, что программистам, как и бомжам, иногда тоже приходится разгребать кучи… Хотя о чем это я! Ведь его величество Интернет – это тоже огромная куча, в которой иногда можно найти очень ценные и полезные вещи…
10.2.3. Сбалансированные деревья
Бинарные деревья поиска предназначены для быстрого поиска данных. Время поиска определяется глубиной дерева. Для деревьев, у которых из каждой вершины выходит ровно две ветви, глубина дерева h = log2n-1, где n количество вершин дерева. Однако некоторые последовательности операций включения или исключения вершин могут привести к двоичным деревьям поиска, структура которых будет вырожденной: состоять из одного поддерева из n элементов. Например, для последовательности загружаемых в дерево поиска данных: 8,10, 14, 13 дерево поиска вырождается в линейный список. Максимальное количество сравнений для поиска вершины в таком дереве равно количеству элементов в дереве (n). Для того чтобы дерево использовалось для быстрого поиска необходимо после каждой вставки или удаления вершины выполнять перестроение дерева, чтобы его высота оставалась минимальной, а само дерево оставалось полным (сбалансированным).
Дерево считается идеально сбалансированным, если для каждой вершины дерева количества вершин в левом и правом поддеревьях различаются не более чем на 1. Пример идеально сбалансированного дерева поиска приведен на рис. 2.
Рис. 2. Идеально сбалансированное дерево
Идеально сбалансированные деревья поиска обеспечивают минимальное время поиска. Однако операции балансировки идеально сбалансированного дерева, которые необходимо выполнять при включении или исключении вершины, требуют больших временных затрат.
При частом включении и/ или исключении вершин поддерживать дерево идеально сбалансированным становится не выгодным из-за больших временных затрат на балансировку. Выходом из такой ситуации является компромисс – менее строгое определение сбалансированности.
Дерево называется сбалансированным, если высоты двух поддеревьев каждой вершины дерева отличаются не более чем на 1. Пример сбалансированного дерева приведен на рис. 3.
Р
ис. 3. Сбалансированное дерево
Это дерево не сбалансировано идеально, но высоты всех поддеревьев отличаются не более чем на 1.
Сбалансированные деревья называют АВЛ-деревьями по первым буквам фамилий авторов: Адельсон-Вельский Г.М. и Ландис Е.М. Согласно теореме, которую доказали Адельсон-Вельский Г.М. и Ландис Е.М. [3, 4], высота сбалансированного дерева никогда не будет превышать высоту идеально сбалансированного дерева более чем на 45% независимо от количества вершин. Например, для 1000000 вершин высота идеально сбалансированного дерева поиска равна 20, а для АВЛ-дерева – 29. При использовании АВЛ-деревьев время на поддержку баланса вершин дерева меньше, чем для идеально сбалансированных деревьев: в среднем балансировка требуется в одном случае из трех включений. Сбалансированные деревья поиска следует использовать тогда, когда поиск информации происходит гораздо чаще, чем включение и исключение данных.
10.2.4. В-деревья
Еще один способ уменьшения времени поиска в больших массивах данных – использование сильно ветвящихся деревьев. Примером использования сильно ветвящегося дерева может служить файловая система. Высота сильно ветвящегося дерева и, следовательно, количество сравнений при поиске в нем меньше, чем для бинарного дерева. Для m-арного дерева поиска загруженного n данными среднее количество сравнений для поиска logmn. Однако проблема балансировки существует и для сильноветвящихся деревьев поиска. Они также могут вырождаться в линейные списки.
В-дерево является особым видом сбалансированного сильно ветвящегося дерева. Оно используется в качестве индексного файла в базах данных. В-дерево 2-го порядка 1 приведено на рис. 4.
Рис. 4. B-дерево порядка 2
В-деревом n-порядка называется сильно ветвящееся дерево поиска, обладающее следующими свойствами:
Листья дерева хранят либо настоящие записи файла данных, либо ключи и адреса записей файла данных. В первом случае В-дерево называется кластерным индексом, а во втором – некластерным индексом.
Все пути от корня дерева до любого листа имеют одинаковую длину: В-дерево сбалансировано по высоте. Сбалансированность В-дерева поддерживается при его эксплуатации.
Каждая внутренняя вершина содержит ключи данных и указатели на поддеревья. Ключи упорядочены по возрастанию. Каждый ключ имеет двух сыновей. В поддереве слева от ключа находятся вершины с меньшими значениями ключа, а в поддереве справа – с большими или равными значениями. Каждая вершина дерева n-порядка (кроме корня) содержит от n до 2n ключей. Количество указателей в вершине на 1 больше, чем количество ключей. Корень может содержать от 1 до 2n ключей. Для первой записи в любой внутренней вершине ключ не указывается. Это делается для экономии памяти и удобства включения.
Поиск в B-дереве – это прохождение от корня к листу в соответствии с заданным значением ключа. Так как дерево сбалансировано по высоте, то для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью.