АВЛ-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
−
'''АВЛ-дерево''' — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
+
{{Определение|definition=
 +
'''АВЛ-дерево''' {{---}} двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
 +
}}
  
−
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962.
+
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.
  
 
== Балансировка ==
 
== Балансировка ==
 +
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>
 +
{{Определение|definition=
 +
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
 +
}}
 +
Указанный результат получается вращениями поддерева данной вершины. Используются 4 типа вращений:
  
−
Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.
+
{| border="1" cellpadding="5" cellspacing="0"
−
 
+
!Тип вращения
−
Используются 4 типа вращений:
+
!Иллюстрация
−
 
+
!Когда используется
−
  1.'''Малое левое вращение'''
+
|-
−
  [[Файл:AVL RR.GIF]]   
+
  |'''Малое левое вращение'''
−
Данное вращение используется тогда, когда h(b) - h(L) = 2 и h(С) <= h(R).
+
|  [[Файл:AVL RR.GIF|2000x150px]]   
−
   
+
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
−
  2.'''Большое левое вращение'''
+
  |-
−
  [[Файл:AVL RL.GIF]]
+
  |'''Большое левое вращение'''
−
Данное вращение используется тогда, когда h(b) - h(L) = 2 и h(С) > h(R).
+
| [[Файл:AVL RL.GIF|2000x150px]]
−
   
+
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
−
  3.'''Малое правое вращение'''
+
  |-
−
  [[Файл:AVL LL.GIF]]   
+
  |'''Малое правое вращение'''
−
Данное вращение используется тогда, когда h(b) - h(R) = 2 и h(С) <= h(L).
+
| [[Файл:AVL LL.GIF|2000x150px]]   
−
   
+
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
−
  4.'''Большое правое вращение'''
+
  |-
−
  [[Файл:AVL LR.GIF]]
+
  |'''Большое правое вращение'''
−
Данное вращение используется тогда, когда h(b) - h(R) = 2 и h(C) > h(L).
+
| [[Файл:AVL LR.GIF|2000x150px]]
−
 
+
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
−
В каждом случае достаточно просто доказать то, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться.
+
|}
−
 
+
В каждом случае достаточно просто показать, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться.
−
Из-за условия балансированности высота дерева О(lg(N)), где N - количество вершин, поэтому добавление элемента требует O(lg(N)) операций.
 
  
 
== Алгоритм добавления вершины ==
 
== Алгоритм добавления вершины ==

Версия 06:42, 21 марта 2011

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


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

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

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

Определение:
Балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев [math]|h(L) - h(R)| = 2[/math], изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева [math]|h(L) - h(R)| \le 1[/math], иначе ничего не меняет.

Указанный результат получается вращениями поддерева данной вершины. Используются 4 типа вращений:

Тип вращения Иллюстрация Когда используется
Малое левое вращение AVL RR.GIF [math]h(b) - h(L) = 2[/math] и [math]h(C) \le h(R)[/math].
Большое левое вращение AVL RL.GIF [math]h(b) - h(L) = 2[/math] и [math]h(c) \gt h(R)[/math].
Малое правое вращение AVL LL.GIF [math]h(b) - h(R) = 2[/math] и [math]h(C) \le h(L)[/math].
Большое правое вращение AVL LR.GIF [math]h(b) - h(R) = 2[/math] и [math]h(c) \gt h(L)[/math].

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

Алгоритм добавления вершины

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

  1. Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
  2. Включения новой вершины в дерево и определения результирующих показателей балансировки.
  3. "Отступления" назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо - балансировка.

Расширим список параметров обычной процедуры вставки параметром-переменной flag, означающим, что высота дерева увеличилась. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { hl - высота левого поддерева, hr - высота правого поддерева } Включение вершины в левое поддерево приведет к

  1. hl < hr: выравняется hl = hr. Ничего делать не нужно.
  2. hl = hr: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется.
  3. hl > hr: теперь hl - hr = 2, - требуется балансировка.

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

Алгоритм удаления вершины

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

Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировки высота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может изменится) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1.

Очевидно, в результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет одного из поддеревьев. Но поиск ближайшего каждый раз требует O(N) операций, отсюда видна очевидная оптимизация: поиск ближайшей вершины производится по краю поддерева. Отсюда количество действий O(log(N)).

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=АВЛ-дерево&oldid=7917»