Принцип работы алгоритма.

ПРИНЦИП РАБОТЫ АЛГОРИТМА.

Рассмотрим бинарное дерево представленное на рис. 6.28 (а), которое состоит только из двух узлов. Включение ключа 7 дает вначале несбалансированное дерево (т.е. линейный список). Его балансировка требует однократного правого (RR) поворота, давая в результате идеально сбалансированное дерево (b). Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным левым (LL) поворотом (d). Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5.

Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (LR); результатом является дерево (e). Теперь при следующем включении потерять сбалансированность может лишь узел 5. Действительно, включение узла 6 должно привести к четвертому виду балансировки: двукратному повороту направо и налево (RL). Окончательное дерево показано на рис.6.35 (а-f).