Как можно видеть из доказательства теоремы, для поиска в сбалансированном дереве будет требоваться больше 25 сравнений, только если дерево содержит хотя бы F28 - 1 = 3 1 78 1 0 узлов.

Рассмотрим, что происходит при вставке нового узла в сбалансированное дерево с использованием алгоритма вставки в дерево 6.2.2Т. Дерево, показанное на рис. 20, остается сбалансированным, если новый узел занимает место [Т], [б], [б], [Т], [То или [1з], но в других случаях потребуется определенная корректировка. Проблемы начинаются, когда имеется узел с фактором сбалансированности +1, правое поддерево которого после вставки становится выше (или, если фактор сбалансированности равен -1, выше становится левое поддерево). Нетрудно видеть, что неприятности возникают только в двух случаях.

Случай 1

Случай 2

(Два других неприятных случая могут быть получены из указанных при зеркальном отражении относительно вертикальной оси.) На этой диаграмме большие прямоугольники а, 7, 6 представляют поддеревья с соответствующими высотами. Случай 1 имеет место, когда новый элемент увеличивает высоту правого поддерева узла Д с /г до /г + 1, а случай 2 - когда увеличивается высота левого поддерева узла В. В поачеднем случае либо /г = О (когда X представляет собой новый узел), либо узел X имеет два поддерева с высотами {h - l,h) или {h,h - l).

Выполнив простые преобразования, можно восстановить баланс в обоих случаях; при этом симметричный порядок узлов дерева сохранится.

Случай 2

В случае 1 мы просто "поворачиваем" дерево налево, присоединяя /? к Л вместо В. Такое преобразование подобно применению ассоциативного закона к алгебраической формуле, заменяющему а(/?7) на {а/З). В случае 2 используется двойной поворот: сначала {Х,В) поворачивается направо, затем {А,Х) - налево. В обоих случаях в дереве требуется изменить лишь несколько ссылок. Кроме того, новые деревья имеют высоту h + 2, точно равную высоте, которая была до вставки. Следовательно, остаток дерева (если таковой имеется), который изначально находился над узлом А, всегда остается сбалансированным.

Рис. 21. Дерево, показанное на рис. 20, после вставки нового ключа R и выполнения балансировки.

Например, если вставить новый узел в позицию [Тт] в дерево, представленное на рис. 20, после однократного поворота получится сбалансированное дерево, показанное на рис. 21 (случай 1). Обратите внимание, что при этом изменились некоторые факторы сбалансированности.

Детали этой процедуры вставки могут быть разработаны различными способами. На первый взгляд кажется, что избежать использования вспомогательного стека невозможно, поскольку требзется запоминать узлы, затронутые при вставке. Однако описанный ниже алгоритм позволяет обойтись без стека и выиграть при этом в скорости работы, если учесть, что фактор сбалансированности узла В в (1) был до вставки равен нулю.

Алгоритм А [Поиск со вставкой по сбалансированному дереву). Дана таблица записей в форме сбалансированного бинарного дерева, описанного выше. Алгоритм (рис. 22) производит поиск данного аргумента К. Если К отсутствует в таблице, в соответствующее место в дереве вставляется узел, в котором содержится К, и дерево при необходимости ребалансируется.

Предполагается, что, как и в алгоритме 6.2.2Т, узлы дерева имеют поля KEY, LLINK и RLINK. Кроме того, имеется новое поле

В(Р) = фактор сбалансированности узла NODE(P),

разность высот правого и левого поддеревьев. В нем всегда содержится только одно из трех значений: +1, О или -1. На вершине дерева по адресу HEAD расположен специальный узел, значение RLINK (HEAD) которого указывает на корень дерева, а LLINK (HEAD) используется для хранения полной высоты дерева (знание высоты не является необходимым дяя этого алгоритма, однако полезно при конкатенации, которая будет обсуждаться ниже). Также полагается, что дерево непустое, т. е. RLINK(HEAD) 7 Л.

Для удобства описания в алгоритме используется обозначение LINK (о, Р) как синоним для LLINK(P) при о = -1 и для RLINK(P) при а = -1-1.

А1. [Инициализация.] Установить Т <- HEAD, S •(- Р •(- RLINK(HEAD). (Пере.менная-указатель Р будет двигаться вниз по дереву; S будет указывать место, где

Al. Инициализация

Поиск

, a:=key(p)

А2. Сравнение K<KEY(P)/ Я \K>KEY(P)

-> Успешное завершение поиска

A3. Перемещение влево

А4. Перемещение вправо

А6. Корректировка

факторов сбалансированности

А7. Балансировка

А8. Однократный поворот

Балансировка

А9. Двукратный поворот

АЮ. Последний штрих

Дерево осталось сбалансированным

Рис. 22. Поиск со вставкой по сбалансированному дереву.

может потребоваться ребалансировка, а Т всегда указывает на родительский по отношению к S узел.)

А2. [Сравнение.] Если К < KEY(P), перейти к шагу A3; если К > КЕУ(Р), перейти к шагу А4; если К = КЕУ(Р), поиск успешно завершен.

A3. [Перемещение влево.] Установить Q <- LLINK(P). Если Q = А, присвоить Q AVAIL и LLINK(P) 4- Q и перейти к шагу А5. В противном случае, если B(Q) ф О, присвоить Т Р и S Q. И, наконец, присвоить Р •(- Q и вернуться к шагу А2.

А4. [Перемещение вправо.] Установить Q •(- RLINK(P). Если Q = А, присвоить Q < AVAIL и RLINK(P) Q и перейти к шагу А5. В противном случае, если B(Q) фО, присвоить T-PhS-Q. И, наконец, присвоить Р •(- Q и вернуться к шагу А2. (Последняя часть этого шага может быть объединена с последней частью шага A3.)

А5. [Вставка.] (Мы только что связали новый узел NODE(Q) с деревом; теперь следует инициализировать его поля.) Установить КЕУ(Р) <- К, LLINK(Q) 4- RLINK(Q) 4- А и B(Q) 4- 0.

А6. [Корректировка факторов сбалансированности.] (В настоящий момент следует из.менить факторы сбалансированности узлов между S и Q с О на ±1.). Если К < КЕУ(З), установить а <- -1; в противном случае установить а <- +1. Затем присвоить R 4- Р 4- LINK (о, S) и при необходимости повторить следую-