Изменения

Перейти к: навигация, поиск

АВЛ-дерево

795 байт убрано, 13:26, 12 июня 2012
Балансировка
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR40 03.GIFpng|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>
|-
|'''Большое левое вращение'''
| [[Файл:AVL RL40 04.GIFpng|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] = 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 и не может увеличиться.
59
правок

Навигация