Поиск в деревьях

Двоичные деревья, сбалансированные по высоте (АВЛ-деревья)

Деревья, сбалансированные по высоте, были предложны Г. М. Адельсоном-Вельским и Е. М. Ландисом, поэтому они также называются АВЛ-деревьями.

Пусть h (T) обозначает высоту двоичного дерева T, то есть длину самого длинного пути от корня к листу. Высота дерева с единственным узлом равна 0, и по определению мы считаем высоту пустого дерева равной –1.

Определение 4.3.8. Будем называть балансом дерева T (или балансом узла, который является корнем этого дерева) bal (T) разность высот его левого Tl и правого Tr поддеревьев:

bal (T) = h (Tl) – h (Tr).

Определение 4.3.9. Двоичное дерево T называется сбалансированным по высоте, если выполнены два условия:

1. | bal (T)| =<1

2. Два поддерева Tl и Tr корня дерева T сбалансированы по высоте.

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

На рис. 1 показаны некоторые сбалансированные по высоте деревья и одно двоичное дерево, не являющееся таковым. Ограничение на высоту поддеревьев обеспечивает близость сбалансированных по высоте двоичных деревьев к полностью сбалансированным двоичным деревьям. Действительно, на рис. 1 (a, б) показаны два «наиболее асимметричных» сбалансированных по высоте двоичных дерева среди деревьев с высотами 1 и 2 соответственно.

Рис. 1. Примеры сбалансированных по высоте двоичных деревьев (а), (б) и несбалансированного по высоте двоичного дерева (в)

Не смотря на то, что сбалансированные по высоте двоичные деревья могут выглядеть разреженными, время поиска, которое они требуют, лишь немного больше, чем в полностью сбалансированных двоичных деревьях. Экспериментальные данные позволяют предположить, что средняя длина внутренних путей в сбалансированном по высоте двоичном дереве с n узлами равна n log2 n + O (n); следовательно, среднее время поиска равно log2 n + O (l),

что асимптотически отличается от среднего времени поиска в полностью сбалансированном двоичном дереве лишь константой.

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

Наиболее асимметричное сбалансированное по высоте двоичное дерево Th высоты h имеет наиболее асимметричное двоичное дерево Th –1 высоты h –1 в качестве одного из своих поддеревьев и наиболее асимметричное двоичное дерево Th –2 высоты h – 2 в качестве другого, как показано на рис. 2. Наиболее асимметричные сбалансированные по высоте двоичные деревья, показанные на рис. 1 (a, б) для h = l и h = 2, построены по правилу Фибоначчи при начальных пустом дереве T –1 и дереве Т 0 с одним узлом. Так, дерево, приведенное на рис. 1 (б), в качестве левого поддерева содержит T 0, а в качестве правого – T 1.

Рис. 2. Структура наиболее ассиметричного сбалансированного по высоте дерева Тh

Обозначая число узлов в Тh через nh и длину внутренних путей в Тh через Ih, получаем неоднородные линейные рекуррентные соотношения с постоянными коэффициентами

и

Для h можно найти

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

Приближенный анализ среднего (в большей степени отражающего истинное положение, чем худший случай) времени успешного поиска Sh = Ih / nh в наиболее асимметричном сбалансированном по высоте двоичном дереве даже более удобен.

Среднее время поиска в наиболее асимметричных сбалансированных по высоте двоичных деревьях:

Теперь можно сказать, что среднее время поиска даже в наиболее асимметричных сбалансированных по высоте двоичных деревьях всего лишь на 4% больше, чем в полностью сбалансированных двоичных деревьях. Заметим, что наиболее асимметричные сбалансированные по высоте двоичные деревья составляют лишь небольшую часть от всех сбалансированных деревьев. Учитывая вышесказанное, а также эмпирически полученные результаты, получаем оценку среднего числа операций при поиске элементов в случайных деревьях, сбалансированных по высоте, равную O (log n).

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

Рис. 3. Пример правого вращения относительно узла B

Каждый узел сбалансированного двоичного дерева имеет баланс 1, –1 или 0. Очевидно, что при вставке нового узла дерево становится несбалансированным, только если этот узел становится левым потомком узла, который имел баланс 1, или правым потомком узла, который имел баланс –1.

Предположим, что в дерево добавлен новый узел, и дерево перестало быть сбалансированным. Рассмотрим поддерево минимальной высоты, корнем которого является узел, в котором произошла разбалансировка. Предположим, что баланс данного узла A (корня поддерева) был равен –1, то есть высота левого поддерева меньше высоты правого (случай положительного баланса аналогичен). Новый узел добавляется в правое поддерево. Как сказано выше, узел A является корнем поддерева минимальной высоты, в котором произошла разбалансировка. Следует отметить, что балансы всех узлов на пути от вершины A до вставленного узла были равны 0. На рис. 4. приведены эти два типа преобразований и показано, как они восстанавливают сбалансированность дерева, нарушенную вставкой элемента. В левых частях рис. 4. (a) и (б) показаны поддеревья сбалансированного по высоте двоичного дерева, в которое только что был включен новый узел. Это включение послужило причиной нарушения ограничения на высоту в узле A. Оказывается, что ограничения на высоту, которые могли быть нарушены в узлах, расположенных в дереве выше, будут восстановлены автоматически.

Рис. 4. Примеры вращения (а) и двойного вращения (б) для восстановления сбалансированности дерева по высоте, нарушенной включением нового узла.

Оба преобразования имеют симметричные варианты

Рассмотрим случай, изображенный на рис. 4. (a). Высоты поддеревьев Т 1, Т 2 и Т 3 равны h – 2. После вставки нового элемента в правое поддерево Т 3 высота поддерева увеличилась на 1 (на рисунке увеличение высоты отмечено серым цветом). В этом случае баланс в узле A становится равным –2. Восстановление баланса производится за счет вращения влево относительно узла A. В полученном поддереве узел B становится отцом узла A, балансы узлов A и B становится равными 0. Будут меняться балансы узлов, лежащих на пути от узла B к вновь вставленному узлу. Поскольку их балансы изначально были нулевыми, то в случае, если из текущего узла на этом пути мы идем в левое поддерево, то баланс меняется на 1, в противном случае на –1. Высота поддерева после преобразования не меняется и остается равной h. Произведенное вращение не изменит балансы всех остальных узлов дерева, при этом вновь полученное дерево будет сбалансированным по высоте.

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

элемента. Баланс узла А был равен –1, а балансы узлов В и С были нулевыми. Высота поддеревьев Т 1, Т 4 равна h – 2, а поддеревьев Т 2, Т 3 равна h – 3. Для демонстрации двойного вращения новый элемент вставляется либо в поддерево Т 2, либо в поддерево Т 3, увеличивая их высоту на единицу, и тем самым изменяя баланс узла A с –1 на –2. Еще раз отметим, что узел A – первый на пути от вновь вставленного узла к корню, где произошла разбалансировка. Чтобы восстановить баланс, сначала производится правое вращение относительно узла C, а затем левое относительно узла A. В результате баланс узла B становится равным нулю. Балансы узлов A и C зависят от того, в какое поддерево добавлялся новый элемент. Если удлинилось поддерево Т 2, то балансы bal (A) = 0 и bal (C) = –1. В случае если удлинилось поддерево Т 3, то балансы bal (A) = 1 и bal (C) = 0. Будут также меняться балансы узлов, лежащих на пути либо от вершины A, либо от вершины C к вновь вставленному узлу. Поскольку балансы узлов, лежащих на этом пути, изначально были нулевыми, то в случае, если из текущего узла идем в левое поддерево, то баланс меняется на 1, в противном случае – на –1. Высота поддерева после преобразования не меняется и остается равной h. Данное преобразование, как и в случае простого вращения, не изменит балансы всех остальных узлов дерева, при этом вновь полученное дерево будет сбалансированным по высоте.

Важно отметить, что:

1. высота поддеревьев до и после вставки элемента осталась неизменной. И, следовательно, после этих локальных преобразований в целом дерево является сбалансированным по высоте;

2. дерево остаётся двоичным деревом поиска.

Дата добавления: 2015-08-09