Изменения

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

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

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