Изменения
→Балансировка
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение''' (''Small left rotation'')
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>
|-
|'''Большое левое вращение''' (Big left rotation'')
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
Малый левый поворот:
rotateleft(node a) {
node b = a.right
a.right = b.left
b.left = a
fixheight(a)
fixheight(b)
}
Большой правый поворот пишется проще:
bigrotateleft(node a) {
rotateright(a.right)
rotateleft(a)
}
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на <tex>1 </tex> и не может увеличиться.
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.
