2015-08-12
477
При балансировке имеют место лишь две принципиально различные ситуации, требующие индивидуального подхода («одинарное» и «двойное» вращения). Оставшиеся варианты могут быть получены симметричным преобразованием этих двух.
Обозначим для удобства баланс в вершине «++», если он равен 2, «- -» – если равен -2 и «
» – если баланс равен 0.
1. «Одинарное вращение»
a) (RR)
b) (LL)
2. «Двойное вращение»
2.1. (RL), узел 
имеет баланс «+2», узел 
– «-1»
a) (RL), узел 
изначально имеет баланс 0:
b) (RL), узел изначально имеет баланс -1:
c) (RL), узел изначально имеет баланс +1:
2.2. (RL), узел имеет баланс «-2», узел – «+1»
В этом случае также имеются три варианта балансировки в зависимости от баланса узла . Они симметричны рассмотренным ранее. Предлагается эти три варианта самостоятельно (в качестве упражнения).
Таким образом, необходимые операции балансировки заключаются полностью в обмене значениями соответствующих ссылок. Фактически ссылки обмениваются «по кругу», что приводит к однократному или двукратному повороту двух или трёх узлов соответственно. Кроме «вращения» ссылок следует также пересчитать показатели сбалансированности узлов.
Пример:
