АВЛ-дерево

АВЛ-дерево

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

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

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

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

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

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

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

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

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

База индукции: m₁ = F₃ - 1 верно, т.к. m₁ = 1, F₃ = 2.

Тогда имеем m_h+1 = m_h + m_h-1 + 1 = F_h+2 - 1 + F_h+1 - 1 + 1 = F_h+3 - 1.

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

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

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

То есть n ⩾ φ^h.

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

log_φn ⩾ h

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

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

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

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