Для работы алгоритма поддержания балансировки требуется в каждом узле хранить показатель сбалансированности, принимающий значения –1, 0, 1,
Рис 44. Два случая нарушения балансировки
и равный разности высот правого и левого поддеревьев узла. В принципе возможны только два случая нарушения балансировки, изображенные на рис 44. Другие "плохие" случаи можно получить вращением вокруг вертикальных осей, проходящих через узлы A и B.
Первый случай имеет место, когда вставка увеличивает высоту правого поддерева узла В с h до h+1. Во втором случае либо h=0 и X – новый узел, либо узел X имеет поддеревья с высотами h, h+1. Преобразования, изображенные на
рис.45 восстанавливают балансировку, сохраняя правильность построения дерева.
Рис. 45 Восстановление балансировки
В обоих случаях в дереве нужно изменить лишь несколько связей. Преобразованные деревья имеют высоту h+2, как до включения нового узла. Следовательно, часть дерева, расположенная над узлам А не изменится. Обратите внимание на тот факт, что порядок следования узлов в обратном порядке до и после преобразования не изменился.
