AOP_Tom3 (1021738), страница 127
Текст из файла (страница 127)
Впрочем, оперативная память становится всв дешевле, а значит, сбалансированные деревья становятся все более и более важным орудием в руках программиста. Вьюета дерева определяется как его максимальный уровень, длина самого длинного пути от корня к внешнему узлу. Бинарное дерево называется сбаяансириеаянмм, если высота левого поддерева любого узла отличается не более чем на х! от высоты правого поддерева. На рис. 29 показано сбалансированное дерево высотой 5 с 17 внутренними узлами; фактор сбаяансирееаяносщи обозначен внутри каждого узла знаками "+", " " и "— ' в ссютветствии с величиной разности между высотами правого и левого поддеревьев (+1, 0 или — 1).
Дерево Фибоиаччи на рис. 8 Рис. 20. Сбалансированное бинарное дерево. в разделе 6.2.1 служит еще одним примером сбалансированного бинарного дерева высотой 5 с 12 внутренними узлами; большинство факторов сбалансированности в атом дереве равны — 1. Дерево знаков зодиака иа рис. 10 в разделе 6.2.2 ис сбалансировано, поскольку для узлов АЦ0АЕ106 и СЕИ1в1 нарушено условие для величины разности высот поддеревьев, Такое определение сбалансированности представляет собой компромисс между оптимальными бинарными деревьями (все внешние узлы которых должны размещаться на двух соседних уровнях) и произвольными бинарными деревьями.
Отсюда естестненным образом возникает вопрос "Насколько далеко от оптимального может оказаться сбалансированное дерево7". Ответ на него гласит, что путь поиска по сбалансированному дереву не превышает пути поиска по оптимальному дереву более чем на 45%.
Теорема А (Лдельсон-Вельский и Ландис). Высота сбалансированногодерева с Х внутренними узламя ограничена значениями )к(Х + 1) и 1.4405 1к(Л + 2) — 0.3277. Доказашельсшво. Бинарное дерево высотой Ао очевидно, не может иметь более 2" внешних узлов; таким образом, Я+1 ( 2", т. е. Л > ~!Е(Ю+1Д для любого бинарного дерева. Для поиска максимального значения А рассмотрим проблему с друтой стороны и зададимся вопросом о минимальном количестве узлов в сбалансированном дереве высотой Ь. Пусть Ть — такое дерево с наименьшим возможным количеством узлов, тогда одно из поддеревьев корня, например левов, имеет высоту 5 — 1, а правое— А — 1 или Ь вЂ” 2.
Поскольку дерево Ть должно иметь минимальное количество узлов, можно считать, что в силу определения Ть левое поддерево представлиет собой дерево Ть и а правое — Ть з. Таким образом, наименьшее возможное количестно узлов среди всех сбалансированных деревьев имеет дерево Фибоначчи (см. определение деревьев Фибоначчн в разделе 6.2.1). Следовательно, Х > г~ з — 1 > фь' з/Л вЂ” 2 и требуемый результат получается так же, как и следствие из теоремы 4.5.3Р. 3 Как можно видеть из доказательства теоремы, для поиска в сбалансированном дереве будет требоваться больше 25 сравнений, только если дерево содержит хотя бы Егв — 1 = 317810 узлов.
Рассмотрим, что происходит при вставке нового узла в сбалансированное дерево с использованием алгоритма вставки в дерево 6.2.2Т. Дерево, показанное на рис. 20, остается сбалансированным, если новый узел занимает место Д4, Е, Де, Дт, Дю или ~~з~, но в других случаях потребуется определенная корректировка. Проблемы начинаются, когда имеется узел с фактором сбалансированности +1, правое поддерево которого после вставки становится выше (нли, если фактор сбалансированности равен — 1, выше становится левое поддерево). Нетрудно видеть, что неприятности возникают только в дву.х случаях.
Случай 2 Л Л~~ ( .!:..'4 (1) Л Случай 1 Л (Два других неприятных случая могут быть получены из указанных при зеркальном отражении относительно вертикальной оси.) На этой диаграмме большие прялюугольники ск, Ц, з, б представляют полдеревья с соответствующими высотами. Случай 1 имеет место, когда новый элемент увеличивает высоту правого полдерева узла В с Ь до Ь + 1, а случай 2 — когда увеличивается высота левого поддерева узла В.
В последнем случае либо Ь = 0 (когда Х представляет собой новый узел), либо узел Х имеет два поддерева с высотами (Ь вЂ” 1, И) или (Ь, Ь вЂ” 1). Выполнив простые преобразования, люжно восстановить баланс в обоих случаях; при этом симметричный порядок узлов дерева сохранится. Случай 2 Т Л Случай 1 В случае 1 мы просто "поворачиваем" дерево налево, присоединяя 17 к А вместо В. Такое преобразование подобно применению ассоциативного закона к алгебраической формуле, заменяющему о(Д7) на (оф)З. В случае 2 используется двойной поворот: сначала (Х, В) поворачивается направо, затем (А, Х) — налево. В обоих случаях в дереве требуется изменить лишь несколько ссылок. Кроме того, новые деревья имеют высоту Ь+2, точно равную высоте, которая бьша до вставки.
Следовательно, остаток дерева (если таковой имеется), который изначально находился над узлом А, всегда остается сбалансированным. Рис. 21. Дерево, показанное на рис, 20, после вставки нового ключа а и выполнения балансировки. Например, если вставить новый узел в позицию Я в дерево, представленное на рис. 20, после однократного поворота получится сбалансированное дерево, показанное на рис. 21 (случай 1).
Обратите внимание, что при этом изменились некоторые факторы сбалансированности, Детали этой процедуры вставки могут быть разработаны различными способами. На первый взгляд кажется, что избежать использования вспомогательного стека невозможно, поскольку требуется запоминать узлы, затронутые при вставке. Однако описанный ниже алгоритм позволяет обойтись без стека и выиграть при этом в скорости работы, если учесть, что фактор сбалансированности узла В в (1) бьш до вставки равен нулю.
Алгоритм А (Поиск со есшоекой па обо онсироеанному дереву). Дана таблица записей в форме сбалансированного бинарного дерева, описанного выше. Алгоритм (рис. 22) производит поиск данного аргумента К. Если К отсутствует в таблице, в соответствующее место в дереве вставляется узел, в котором содержится К, и дерево при необходимости ребачансируется.
Прсдполагается, что, как и в алгоритме 6.2.2Т, узлы дерева имеют поля КЕУ, ЕЕ1ИК и НИИК. Кроме того, имеется новое поле Н(Р) = фактор сбалансированности узла ИОНЕ(Р), разность высот правого и левого поддеревьев. В нем всегда содержится только одно из трех значений: +1, 0 или — 1. На вершине дерева по адресу НЕАН распо.южен специальный узел, значение НБ1ИК(НЕАН) которого указывает на корень дерева, а ЬЫИК(НЕАН) используется для хранения полной высоты дерева (знание высоты не является необходимым для этого алгоритма. однако полезно при конкатенации, которая будет обсуждаться ниже). Также полагается, что дерево ненустое, т, е. И.ХИК(НЕА0) ф Л.
Для удобства описания в алгоритме используется обозначение 01ИК(а,Р) как синоним для ЕЕ1ИК(Р) при а = — 1 и для НЕ1ИК(Р) при а = +1. А1.(инициализация.) Установить Т э в НЕАН, Б +- Р +- Н1.1МК(НЕАН). (Перемепнаяуказатель Р будет двигаться вниз по дереву; Я будет указывать место, где Поиск А1. Инициализация Аз. Сравнение К=КЕУ(Р) Условное еаверпение поиске К >КЕУ(Р) РС <КЕУ(Р) А4. Переме- Шеиие вправо АЗ. Перемен(ение влево Лист найден Вставка: Лист найден Ав. Вставка Балансировка АК. Однократный поворот Аб Корректировка факторов сбалансированности АУ.
Балан- сировка А10. Последний штрих А9 Двукратный поворот Дерево осталась сеалансироваииыи Рис. 22. Поиск са вставной па сбалансированному дереву. может потребоваться ребалансировка, а Т всегда указывает на родительский по отношению к Б узел.) А2. [Сравнение.[ Если К < КЕУ(Р), перейти к шагу АЗ; если К > КЕУ(Р), перейти к шагу А4; если К = КЕЧ(Р), поиск успепшо завершен. АЗ. [Перемещение влево.) Установить Ц 4 — ШИК(Р).
Если Ц = Л„присноить Ц ~ АЧА15 и ЕЕ1ИК(Р) е- Ц и перейти к шагу А5. В противном случае, если В(Ц) ф. О, присвоить Т + — Р и Б +- Ц. И, наконец, присвоить Р +- Ц и вернуться к шагу А2. А4. [Перемещение вправо.] Установить Ц 4- НЕ1ИК(Р). Если Ц = Л, присвоить Ц ~ КЧКП. и ВЕ1ИК(Р) +- Ц и перейти к шагу А5. В противном случае, если В(Ц) ~ О, присвоить Т +- Р и Б +- Ц. И, наконец, присвоить Р 4 — Ц и вернуться к шагу А2. (Последняя часть этого и~ага может быть объединена с последней частью шага АЗ.) А5. [Вставка.) (Мы только что связали новый узел ИОВЕ(Ц) с деревом; теперь следует инициализировать его поля.) Установить кеу(Ц) 4 — К, ЕБ1ик(Ц) е- ЕЕТИК(Ц) 4 — Л и В(Ц) +- О.
Аб. [Ко)еректировка факторов сбалансированности.[ (В настоящий момент следует изменить факторы сбалансированности узлов между Б и Ц с О на ш1.) Если К < КЕХ(Я), установить ц +- — 1; в противном случае установить а +- +1. Затем присвоить В 4 — Р 4- Е1ИК(ц, Я) и при необходимости повторить следую- шую операцию несколько раз, пока Р не станет равным Ц: если К ( КЕТ(Р), установить В(Р) +- — 1 и Р ~- Ы.1ИК(Р); если К > КЕТ(Р), устаяовить В(Р) е- +1 и Р +- Н!.1ИК(Р). (Если К = КЕТ(Р), то Р = ц и перейти к следующему шагу.) АТ. [Балансировка.] На этом шаге возможны несколько вариантов.
1) Если В(Я) = 0 (дерево стало вылив), установить В(Б) е- а, 1Л.1ИК(НЕАВ) +- ЕЕ1ИК(НЕАО) + 1 и прекратить выполнение алгоритма. Н) Если В(Б) = -о, (дерево сталоболее сбалансированным), установить В(Б) +-0 и прекратить выполнение алгоритма. !и) Если В(Я) = а (дерево разбалансировано), перейти к шагу Л8 при В(Н) = а или к шагу А9 при ВОН) = -а. (Случай (ш) соответствует ситуации, приведенной в (1), при а = +1; Я и Н указывают на узлы А и В соответственно, Е1ИК( — а, Я) указывает на а ит,д.) А8. [Однократный поворот ] Установить Р е- Н, Е1ИК (а, Б) е-1 1ИК( — а, Н), 11ИК ( — а, Н) е-Б, В(Б) е- В(Н) е- О. Перейти к шагу А10. А9. [Двукратный поворот] Установить Р < — ЫИК( — а, Н), 11ИК( — а, Н) < — 11ИК(а, Р), 11ИК(а,Р) +- Н, ! 1ИК(а, Б) < — Е1ИК( — а,Р), 11ИК( — а,Р) + — Б; присвоить сначала ( — а,0), если В(Р) = а; (В(Б),В(Н)) +- ( 0,0), если В(Р) = 0; ( О,а), если В(Р) = — а; (3) а затем — В(Р) +- О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
