Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 26
Текст из файла (страница 26)
Поскольку дерево Ть должно иметь минимальное количество узлов, можно считать, что в силу определения Ть левое поддерево представляет собой дерево Ть и а правое —. Ть з. Таким образом, наименьшее возможное количество узлов среди всех сбалансированных деревьев имеет дерево Фибоначчи (см, определение деревьев Фибоначчи в разделе 6.2.1). Следовательно, Л~ > Гл+т — 1 > Ф"~ ~Л вЂ” 2 и требуемый результат получается так же, как и следствие нз теоремы 4.5.3г. 5 Как можно видеть из доказательства теоремы, для поиска в сбалансированном дереве будет требоваться больше 25 сравнений, только если дерево содержит хотя бы Езэ — 1 = 317810 узлов. Рассмотрим, что происходит при вставке нового узла в сбалансированное дерево с использованием алгоритма вставки в дерево 6.2.2Т, Дерево, показанное на рис.
20„ остается сбалансированным, если новый узел занимает место Е, Е, (а~, '(т), Я или Я, но в других случаях потребуется определенная корректировка. Проблемы начинаются, когда имеется узел с фактором сбалансированности +1., правое подав. рево которого после вставки становится выше (или, если фактор сбалансированности равен -1, выше становится левое поддерево). Нетрудно видеть, что неприятности возникают только в двух случаях.
Случай 2 ь ! ьег ж Случай 1 Ь Случай 1 ! В случае 1 мы просто "поворачиваем" дерево налево, присоединяя р' к А вместо В. Такое преобразование подобно применению ассоциативного закона к алгебраической формуле, заменяющему а(ду) на (с4) ~. В случае 2 используется двойной поворот: сначала (Х, В) поворачивается направо, затем (А, Х) — налево. В обоих случаях в дереве требуется изменить лишь несколько ссылок. Кроме того, новые деревья имеют высоту 0+2, точно равную высоте, которая была до вставки. Следовательно, остаток дерева (если таковой имеется), который изначально находился над узлом А, всегда остается сбалансированным. (Два других неприятных случая могут быть получены из указанных при зеркальном отражении относительно вертикальной оси.) На этой диаграмме большие прямоугольники а, О, у, 6 представляют ппдлеревья с соответствуннцими высотами.
Случай 1 имеет место, когда новый элемент увеличивает высоту правого поддерева узла В с и до Ь + 1, а случай 2 -- когда увеличивается высота левого поддерева узла В. В последнем случае либо Ь = 0 (когда Х представляет собой новый узел), либо узел Х имеет два поддерева с высотами (Ь вЂ” 1, л) или (л, й-1). Выполнив простые преобразования, можно восстановить баланс в обоих случаях; при этом симметричный порядок узлов дерева сохранится. Рис. 21.
Дерево, показанное яа рнс, 20, после вставки нового ключа И и выполнения балансировки, Например, если вставить новый узел в позицию [11] в дерево, представленное на рнс. 20, после однократного поворота получится сбалансированное дерево, показанное на рис. 21 (случай 1). Обратите внимание, что при этом изменились некоторые факторы сбалансированности. Детали этой процедуры вставки могут быть разработаны различными способами. На первый взгляд кажется, что избежать использования вспомогательного стека невозможно,поскольку требуется запоминать узлы, затронутые при вставке. Однако описанный ниже алгоритм позволяет обойтись без стека и выиграть при этом в скорости работы, если учесть, что фактор сбалансированности узла В в (1) был до вставки равен нулю.
Алгоритм А (Поиск со вставкой па сбалансированному дереву). Дана таблица записей в форме сбалансированного бинарного дерева, описанного выше. Алгоритм (рис. 22) производит поиск данного аргумента К. Если К отсутствует в таблице, в соответствующее место в дереве вставляется узел, в котором содержится Ь', н дерево прн необходимости ребалансируется. Пре;нюлагается, что, как и в алгоритме 6.2.2Т, узлы дерева имеют поля КЕХ, 1Л.1ИК и Н1.1ИК. Кроме того., имеется новое поле В(Р) = фактор сбалансированности узла МОВЕ(Р), разность высот правого и левого поддеревьев.
В нем всегда содержится только одно иэ трех значений: +1, 0 или -1. На вершине дерева по адресу НКАО расположен специальный узел, значение Н(.1МК(НКАО) которого указывает на корень дерева, а 1Л.1МК(НКАО) используется для хранения полной высоты дерева (знание высоты не является необходимым дэя этого алгоритма, однако полезно при конкатенации, которая будет обсуждаться ниже). Также полагается, что дерево непусьчае, т.
е. Н 1ИК(НЕАО) р А. Для удобства описания в алгоритме используется обозначение 01МК(а,Р) как синоним для )1.1ИК(Р) при а — — — 1 и для Н(,1МК(Р) прн а = +1. А1.~Инициализация.] Установить 1 е- НЕАО, 3 +- Р ь- Н1.1МК(НЕАО). (Переменная- указатель Р будет двигаться вниз по дереву; Б будет указывать место, где Рис.
22. Поиск со вставкой по сбалансированному дереву, может потребоваться ребалансировка, а Т всегда указывает на родительский по отношению к Б узел,) А2. [Сравнение.) Если К < КИТ(Р), перейти к шагу АЗ; если К > КБТ(Р), перейти к шагу А4; если К = КВТ(Р), поиск успешно завершен. АЗ. [Перемещение влево.) Установить Ц ~- 1Л.1ИК(Р).
Если Ц = А, присвоить Ц ~ атаХХ. и 1Л.ХИК(Р) +- Ц и перейти к шагу А5. В противном случае, если В(Ц) Р' О, присвоить Т е- Р и Б ~ — Ц. И, наконец, присвоить Р е- Ц и вернуться к шагу А2. А4. [Перемещение вправо.) Установить Ц +- Ы.ХИК(Р). Если Ц = Л, присвоить Ц С= АЧАХ(. и КЫМК(Р) +- Ц и перейти к шагу А5. В противном случае, если В(Ц) ф О, присвоить Т < — Р и Б <- Ц. И, наконец, присвоить Р +- Ц и вернуться к шагу А2. (Последняя часть этого шага может быть объединена с последней частью шага АЗ.) А5. [Вставка.) (Мы только что связали новый узел ИОВЕ(Ц) с деревом; теперь следует инициализировать его поля.) Установить КЕТ(Ц) +- К, ХХ,ХИК(Ц) е- Ы.ХИК(Ц) +- А и В(Ц) +- О.
Аб. [Х(орректировка факторов сбалансированности.) (В настоящий момент следует изменить факторы сбалансированности узлов между Б и Ц с О на а1.), Если К < КВТ(Б) „установить а +- -1; в противном случае установить а +- +1. Затем присвоить В е- Р <- 1.1МК(а, Б) н при необходимости повторить следую- шую операцию несколько раз, пока Р не станет равным Ц: если К < КЕТ(Р), установить В(Р) +- -1 н Р+- ЬЫИК(Р); еигн К > КЕТ(Р), установить В(Р) г-+1 и Р +- И.1ИК(Р). (Если К = КЕТ(Р), то Р = Ц и перейти к следующему шагу.) АТ. [Балансировка.] На этом шаге вгвможны несколько вариантов.
() Если В(3) = 0 (дерево стало выше), установить В(3) г — а,. Ы,1ИК(НЕа0) < — 1Л,1ИК(ВЕЛО) + 1 и прекратить выполнение алгоритма. й) Если В(3) = — а (дерево стало более сбалансированным), установить В(3) +-0 и прекратить выполнение алгоритма. ш) Если В(3) = а (дерево разбалансирована), перейти к шагу АБ при ВО() = а или к шагу А9 при В(Н) = — а. (Случай (гп) соответствует ситуации, приведенной в (1), прн а = +1; Б и Н указывают на узлы Л и В соответственно, 1.1ИК(-а,Б) указывает на а и т. д.) АВ. (Однократньгй поворот.] Установить Р г- Н, 1.1ИК(а, 3)+-1.1ИК(-а, Н), 11ИК(-а„Н) +- Б, В(3) +- В(Н) +- О, Перейтн к шагу А10.
А9. Двукратный поворот] Установить Р г-1 |ИК( — а, Н), 11ИК(-а, Н) г- ПИК(а, Р), 11ИК(а,р) +- Н, 11ИК(а,Б) < — 11ИК(-а,Р), ЫИК(-а,р) +- Б; присвоить сначала (-а,О), если В(Р) = а; (В(3),В(Н)) <- ( О,О), если В(Р) = О; ( О,а)„если В(Р) = -а; а затем — В(Р) +- О. А10. (Последний штрих.] (Балансирующее преобразование (1) в (2) завершено; Р указывает на корень нового поддерева, а Т -- на родительский по отношению к корню старого поддерева узел 3.) Если Б = Н1.1ИК(Т), следует установить НЕТИК(Т) г- Р; в противном случае следует установить 11.1ИК(Т) г- Р. 1 Этот алгоритм достаточно длинный, однако разделяется на три простые части: на шагах А1-А4 осуществляется поиск, на шагах А5-А7 — вставка нового узла н на шагах АБ-А10 при необходимости ребэлансируется дерево.
Тот же алгоритм может использоваться и для прошишмя деревьев (см. упр. 6.2.2-2). Известно, что для этого алгоритма требуется около С!оК Аг единиц времени, где С вЂ” некоторая константа. Однако следует оценить ее величину, чтобы знать, при каких Ж использование сбалансированных деревьев становится эффективнее других алгоритмов. Приведенная ниже К1Х-реализация алгоритма позволяет приступить к решению этого вопроса. Программа А (Поиск со всшавкой по сбалансированному дереву). Эта программа, реализующая алгоритм А, использует узлы дерева в следующем формате: (4) гА гн К, г11 ш Р, г)2 =- ц, г13 Рд Н, г14 аз Б, г15 и Т.
Код шагов А7-А9 дублируется, так что значение а используется в программе в неявном виде. 01 В ЕЦЦ 0:1 03 111ИК ЕЦВ 2:3 9Я 08 96 бб 97 98 99 10 П 12 18 Ц 16 16 17 18 19 20 21 22 28 21 26 26 27 28 а9 80 НПИК ЗТАНТ 4Н 1Н 2Н 5Н 1Н бН ЕЦО 4:б (1)А К ЕМТ5 НЕАО Е02 0,5(НПМК) ЯМР 2Р (,02 О, 1 (НПИК) 122 бр (.ОХ Ог2(В) ЯХХ *+3 ЕМТ5 0,1 кита о,2 еит1 0,2 СИРА 1,1 10 4В ЯЕ ЗОССЕЗЗ ии О,1(Е11ИК) 12ИХ 1В 502 АУА11 122 ОУЕНРЕОН (.ОХ Ог2(НПМК) ЗТХ АЧАП. зтА 1,2 зте о 2 ЯЕ 1Р зт2 0,1(нпмк) ЯИР в+2 ЗТ2 0,1(Ы.|ИК) СМРА 1,4 1 1 1 1 С2 С2 С вЂ” 1 С вЂ” 1 П вЂ” 1 1) С С С С1 С1 — Я С1-Я 1 — Я 1 — Я 1 — Я 1 — Я 1 — Я 1 — Я 1 — Я А А 1 — Я вЂ” А 1 — Я А.
'я явяяяя, т+- неАО. О +- ВЕУИК(НЕАВ) . Переход к А2 с 3 с Р с О. А4. Пе е е ение во аео. 0 а-%.1ИК(Р). Переход к шагу Аб при Ц = Л. гХ +- В (О) . Переход, если В (0) = О. т а- Р. 3 а-о. Р «-Ц. ~2 аа~ Переход к шагу А4, если К > КЕТ(Р) . Выход при К = КЕУ(Р).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
