689
правок
Изменения
м
Нет описания правки
1.'''Малое левое вращение'''
[[Файл:AVL LRRR.GIF]] Данное вращение используется тогда, когда h(высота b) -поддерева - высота h(L) = 2 и высота h(С ) <= высота h(R).
2.'''Большое левое вращение'''
[[Файл:AVL BRRL.GIF]]Данное вращение используется тогда, когда h(высота b) -поддерева - высота h(L) = 2 и высота c-поддерева h(С) > высота h(R).
3.'''Малое правое вращение'''
[[Файл:AVL LL.GIF]]
Данное вращение используется тогда, когда h(высота b) -поддерева — высота h(R) = 2 и высота h(С ) <= высота h(L).
4.'''Большое правое вращение'''
[[Файл:AVL BLLR.GIF]]Данное вращение используется тогда, когда h(высота b) -поддерева - высота h(R) = 2 и высота c-поддерева h(C) > высота h(L).
В каждом случае достаточно просто доказать то, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться.
Из-за условия балансированности высота дерева О(lg(N)), где N- количество вершин, поэтому добавление элемента требует O(lg(N)) операций.
== Алгоритм добавления вершины ==
