Изменения
→Балансировка
== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>
{| border="1" cellpadding="5" cellspacing="0"
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>
или
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>
|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>
или
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>
или
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.
или
<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>
<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>
|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>
или
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>
или
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|
<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.
