Поддержание балансировки

Для работы алгоритма поддержания балансировки требуется в каждом узле хранить показатель сбалансированности, принимающий значения –1, 0, 1,

Рис 44. Два случая нарушения балансировки

и равный разности высот правого и левого поддеревьев узла. В принципе возможны только два случая нарушения балансировки, изображенные на рис 44. Другие "плохие" случаи можно получить вращением вокруг вертикальных осей, проходящих через узлы A и B.

Первый случай имеет место, когда вставка увеличивает высоту правого поддерева узла В с h до h+1. Во втором случае либо h=0 и X – новый узел, либо узел X имеет поддеревья с высотами h, h+1. Преобразования, изображенные на

Рис. 45 Восстановление балансировки

В обоих случаях в дереве нужно изменить лишь несколько связей. Преобразованные деревья имеют высоту h+2, как до включения нового узла. Следовательно, часть дерева, расположенная над узлам А не изменится. Обратите внимание на тот факт, что порядок следования узлов в обратном порядке до и после преобразования не изменился.