АВЛ-дерево

Материал из Public ATP Wiki
Версия от 03:44, 25 мая 2020; Algocourselecturenotes (обсуждение | вклад) (Новая страница: «==АВЛ-дерево== ===Определение и свойства=== '''АВЛ-дерево''' - сбалансированное по высоте двоич…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

АВЛ-дерево

Определение и свойства

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

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

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

Лемма о высоте

Пусть mh - минимальное число вершин в АВЛ-дереве высотой h, тогда mh = Fh+2 - 1, где Fh - h-ое число Фибоначчи.

Доказательство леммы

Из свойств АВЛ-дерева следует, что mh+2 = mh + mh+1 + 1 (два поддерева высотами h и h+1 и их вершина-родитель).

Докажем по индукции равенство mh = Fh+2 - 1.

База индукции: m1 = F3 - 1 верно, т.к. m1 = 1, F3 = 2.

Тогда имеем mh+1 = mh + mh-1 + 1 = Fh+2 - 1 + Fh+1 - 1 + 1 = Fh+3 - 1.

Таким образом, равенство mh = Fh+2 - 1 доказано.

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

Fh = Ω(φh), φ=(√5+1)/2.

То есть n ⩾ φh.

Прологарифмировав обе части, получим:

logφn ⩾ h

Таким образом, высота АВЛ-дерева - O(log n).

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

Для поддержания сбалансированности дерева будем в каждой вершине хранить разность высот её поддеревьев diff[i].

Балансировка вершины - операция, которая в случае, если разность высот правого и левого поддеревьев АВЛ-дерева равна 2, изменяет связи "предок-потомок" в поддеревьях данной вершины так, что разность вершин в данном дереве составляет по модулю ⩽ 1. Операция осуществляется посредством вращения поддерева данной вершины.