ВУЗ:
Составители:
116
следнем случае либо h = 0 (Х представляет собой новый узел), либо узел
Х имеет два поддерева с высотами (h – 1, h) или (h, h – 1). Отметим, что
два других случая потери сбалансированности бинарного дерева могут
быть получены из указанных на рис. 41 деревьев при зеркальном отраже-
нии относительно вертикальной оси.
Рис. 41. Два случая потери сбалансированности
Выполнив простые преобразования, как показано на рис. 42, можно
восстановить баланс в обоих случаях. При этом симметричный порядок
узлов дерева сохранится.
Рис. 42. Два случая восстановления сбалансированности
В случае а) дерево просто «поворачивают» налево, присоединяя
поддерево β к узлу A вместо В. Такое преобразование подобно примене-
нию ассоциативного закона к алгебраической формуле, заменяющему
α(βγ) на (αβ)γ. В случае б) используется двойной поворот: сначала (X, В)
поворачивают направо и затем (A, X) – налево. В обоих случаях в дереве
требуется изменить лишь несколько ссылок. Кроме того, новые деревья
имеют высоту h + 2, точно равную высоте, которая была до вставки. Сле-
довательно, остаток дерева (если таковой имеется), который изначально
находился над узлом A, всегда остаётся сбалансированным.
++
A
–
B
α
h
δ
h
X
β
h
–
1
γ
h
б)
++
+
A
B
α
h
β
h
γ
h+1
а)
•
•
B
A
α
h
β
а)
γ
h+1
б)
α
h
A
β
•
X
B
γ
δ
Страницы
- « первая
- ‹ предыдущая
- …
- 114
- 115
- 116
- 117
- 118
- …
- следующая ›
- последняя »
