Главная » Java, Структуры данных и алгоритмы » AVL-деревья

0

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

Определение

В определение бинарного поискового дерева в качестве простой поправки добавляется правило, которое обеспечивает логарифмическую высоту дерева. В этом разделе в качестве такого правила рассматривается свойство сбалансированности по высоте (height-balance property), характеризующее структуру бинарного поискового дерева Т с точки зрения высот его составных узлов (см. п. 6.2.2, где обосновывается высота узла как максимальная длина пути от узла до его крайнего простого узла).

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

Любое бинарное дерево Т, удовлетворяющее этому свойству, будет считаться AVL-деревом, названным в соответствии с инициалами его создателей Adelson-Velskij и Landis (Адельсон-Вельский и Ландис). Пример такого AVL-дерева приведен на рис. 9.8.

Рис. 9.8. Пример AVL-дерева. Внутри узлов показаны ключи, рядом с узлами — высота каждого из них

Естественным следствием свойства сбалансированности является то, что любая ветвь AVL-дерева тоже представляет собой AVL-дерезо. Еще одно важное следствие этого свойства — возможность поддерживать сравнительно малую высоту, как отмечено в следующем утверждении.

Утверждение 9.2. Высота AVL-дерева Т, хранящего п объектов, составляет 0(log п).

Доказательство. Вместо определения верхнего предела высоты AVL-дерева гораздо легче решить противоположную задачу и выяснить нижний предел на минимальном количестве составных узлов n(h) AVL-дерева с высотой h. Покажем, что n(h) возрастает как минимум экспоненциально, то есть n(h) есть Q(ch) для константы с > 1. Исходя из этого, несложно показать, что высота AVL-дерева, хранящего п ключей, составляет 0(log п).

Для начала заметим, что п( 1) = 1 и п(2) = 2, поэтому AVL-дерево высотой 1 должно иметь как минимум один составной узел, a AVL-дерево высотой 2 как минимум два составных узла. Тогда AVL-дерево с высотой h > 3 и минимальным количеством узлов будет выглядеть так, что обе его ветви также являются ми с минимальным количеством узлов: одна — с высотой h – 1, и другая — с высотой h – 2. Принимая во внимание корень, получим следующую формулу, связывающую n(h) с n(h – 1) и n(h – 2) при h > 3:

Теперь читатель, знакомый с прогрессией Фибоначчи (п. 2.2.3 и упражнение 3-3.12), увидит, что n(h) является экспоненциальной функцией от h. Для всех остальных значений продолжим доказательство.

Формула 9.1 предполагает, что n(h) — строго возрастающая функция h. Таким образом, известно, что п{п -1) > п(п – 2). Заменяя n(h-l) на n(h – 2) в формуле 9.1 и отбрасывая 1, получим для h > 3

Формула 9.2 показывает, что n(h) по крайней мере удваивается с каждым увеличением h на 2, что означает (интуитивно) n(h) экспоненциальное возрастание. Чтобы показать это формально, применим формулу 9.2 несколько раз подряд для серии неравенств:

To есть n(h) > 2′ n(h – 2/) для любого целого числа /, такого, что h – 2/ >1. Так как значения п( 1) и п(2) уже известны, выбираем / таким, что h – 2/ равно 1 или 2. То есть применим

Рис. 9.10. Схематическая иллюстрация операции трехузловой реструктуризации (фрагмент кода 9.6). Части (а) и (Ь) показывают разовую ротацию, части (с) и (d) — двойную ротацию

Алгоритм restructure (х):

Input: узел х бинарного поискового дерева Т, имеющий родительский элемент у, родительским элементом которого, в свою очередь, является z.

Output: дерево Т после трехузловой реструктуризации (соответствующей одинарной или двойной ротации), включающей узлы х, у и z.

1.    Положим, что (а, Ь, с) — перечисление (симметричное) слева направо узлов х, уи z. Также допустим, что (Tq, Т\, 7з) — перечисление (симметричное) слева направо четырех ветвей х, у и z, корнями которых х, у и z не являются.

2.    Заменим ветвь, растущую из z, новой ветвью, растущей из Ь.

3.    Пусть а будет левым дочерним элементом Ъ, a 7q и Т\ — левой и правой ветвями а соответственно.

4.    Пусть с будет правым дочерним элементом b, а Т2 и Т3 — левой и правой ветвями с соответственно.

Фрагмент кода 9.6. Операция трехузловой реструктуризации бинарного поискового дерева

Модификация дерева Г, вызванная операцией реструктуризации, официально называется ротацией (rotation) благодаря геометрическому способу представления изменений в Т. Если b = у (см. фрагмент кода 9.6), метод трехузловой реструктуризации называется разовой ротацией (single rotation), так как он отображает ротацию у и z (см. рис. 9.10, а-b). И наоборот, если b = х, операция трехузловой реструктуризации будет называться двойной ротацией (double rotation), так как отображает сначала ротацию х и у, а затем z (см. рис. 9.10, c-d и рис. 9.9). Некоторые исследователи считают, что это два самостоятельных метода, каждый из которых имеет по два симметричных типа. Однако авторы объединяют все четыре типа ротации в одну операцию трехузловой реструктуризации. Но, независимо от представления, заметим, что данный метод модифицирует «семейные» отношения 0(1) узлов в дереве Г, при этом сохраняя симметричный порядок прохода всех узлов в Т.

Кроме того, что при такой реструктуризации сохраняется свойство упорядоченности, при изменении высоты Г сохраняется и свойство сбалансированности. Напомним, <что метод restructure(x) необходимо выполнять, поскольку z, «дедушка» х, перестал быть сбалансированным. Более того, нарушение баланса произошло из-за того, что один из дочерних элементов узла х имеет слишком большую высоту по сравнению с высотой другого дочернего элемента узла z. В результате ротации передвигаем «большого сына» узла х вверх, при этом сдвигаем «маленького сына» узла г вниз. Таким образом, после выполнения restructure(x) все узлы в ветви, растущей из узла, названного b, сбалансированы (см. рис. 9.10).

Таким образом локально восстанавливаем свойство сбалансированности высоты для узлов х, у и z- И одновременно, так как после ввода нового объекта ветвь, растущая из Ьу замещает радее произдаставд1ую из z и длиннее на одну фалангу, все предшественники z, бывшие до этого несбалансированными, снова становятся сбалансированными (см. рис. 9.9). А значит, такая реструктуризация также восстанавливает свойство сбалансированности глобально (то есть по всему дереву). Доказательство этого читателю предлагается осуществить при выполнении упражнения 3-9.11.

Удаление

Как й в случае со словарной операцией insertltem, начинаем реализацию словарной операции removeElement в AVL-дереве применением ал- • горитма выполнения этой операции на обычном бинарном поисковом дереве. При этом возникает та же проблема — возможность нарушения свойства сбалансированности по высоте. В частности, после удаления составного узла с помощью операции removeAboveExternal и перемещением вверх в эту позицию одного из дочерних элементов в дереве Г может появиться несбалансированный узел на пути от родительского элемента w удаленного объекта до корня дерева Г (см. рис. 9.11, а). И действительно, в большинстве случаев так и случается (обоснование чему оставлено для рассмотрения в упражнении 3-9.10).

Как и при вводе, используем трехузловую реструктуризацию для восстановления баланса дерева Т. В частности, пусть z будет первым несбалансированным узлом, обнаруженным на пути от w к корню Т. Пусть у будет дочерним элементом z с большей высотой (заметим, что узел у является дочерним элементом узла г, который не является предшественником узла w), ах будет дочерним элементом у с большей высотой. Выбор х не обязательно уникален, так как ветви у могут иметь одинаковую высоту. В любом случае выполняется операция restructure(x), чтобы восстановить баланс высоты локально в ветви, первоначально произраставшей из z, а теперь из узла, временно названного b (см. рис. 9.11, Ь).

К сожалению, в результате реструктуризации высота ветви, вырастающей из b, может уменьшиться на 1, и предшественники b также перестанут быть сбалансированными. Таким образом, разовая трехузловая реструктуризация после удаления вовсе не обязательно приводит к восстановлению баланса во всем дереве. Поэтому после балансировки z продолжаем двигаться по Г в поисках несбалансированных узлов. При отыскании такового снова выполняется реструктуризация и продолжаем поиск. И так до корня Т. Но, так как высота Г составляет 0(lpg п), где п — количество объектов, то, согласно утверждению 9.2, 0(log п) трехузловых реструктуризации достаточно, чтобы восстановить свойство сбалансированности высоты.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии