Изменения

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

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

Можно показать, что в AVL-дереве высоты <tex>h</tex> не менее, чем <tex>F_h = \Omega(\varphi^h)</tex> вершин, где <tex>F_h - h</tex>-ое число Фиббоначи, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин - <tex>O(\log{n})</tex>.

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

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

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