52
правки
Изменения
Нет описания правки
'''АВЛ-дерево''' (''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.
== Балансировка ==
'''Балансировкой вершины''' ('' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>
!Расстановка балансов
|-
|'''Малое левое вращение'''(''Small left rotation'')
| [[Файл:avl_u1.jpg|2000x200px]]
|
|-
|'''Большое левое вращение'''(Big left rotation'')
| [[Файл:avl_u2.jpg|2000x200px]]
|
