AOP_Tom3 (1021738), страница 203
Текст из файла (страница 203)
(Это элегантное решение предложено Р. Е Таржаном (В. Е. Тат)ал), 51СОМР 6 (1977), 639.) Внимание. Если числа !а, ..., 1„не соотнетствуют никакому бинарному дереву, алгоритм зацнклится. 45. Представить рабочий массив Ро,, Р~ в виде списка с двойнымн связями, коларый также имеет связи со сбалансированным деревом (см, раздел 6.2.3). Если "попарно убывающие" веса равны Ча, ..., Ч~ с Ч, в корне дерева, можно перейти по дереву влево или вправо на основании значений Ч, и Ч, лл; двойные связи обеспечивают мгновенный доступ к Чгй ь (Поля КАИК не являются необходимыми; при чередовании сохраняется симметричный порядок, а потому вносить изменения в двойные связи не нужно.) Отдельные семейства весов, для которых задача может быть решена за время 0(п), были представлены Ху (Ни) и Моргентвлером (Мо»Кеи»Ьа)ег) в Ъессиге №сез ш Сотр.
Яс!. 1120 (1996), 234-243; однако неизвестно, достаточно ли времени 0(п) в общем случае. 46. См. !РЕЕ Тгапз. С-23 (1974), 268-271; кроме того, см. упр. 6.2.3 — 21. 47. См. А!»епЬайпр ав») МеЫЬогп, 1АСМ 27 (1980), 412 — 427. 48. Не позволяйте сложному анализу случаев )7 = 3 (боиввзев аис) КпиСЬ, 1. Сотр. Яузй Яс!. 16 (1978), 301-322) н )7 = 4 (Ваева-Уайеэ, В1Т 29 (1989), 378-394) запугать вас! В этой области достигнут определенный прогресс (см. ЬоисЬап), Вавбг)апагппаиапа, апс) БсЬойй, ТЬеог. Сотр. Яс!. 93 (1992), 201 — 225). 49. Этот вопрос был впервые исследован Дж. М.
Робсоном (1. М. ВоЬэоп) (Аилггабал Сотр. а. 11 (1979), 151-153), Б. Пнттелем (В. Р!»йе!) (з. Ма»Ь. Апа!. Арр!Ы. 103 (1984), 461 — 480) и Люком Девроел» (Ьис 1)етгоуе) (.ИСМ 33 (1986), 489-498; Асса 1лб 24 (1987), 277 — 298), которые получили предельные формулы, выполняющиеся с вероятностью -й 1 прн г» -й ао; см. Н. М. МаЬтаи»), Ега!ис(ал о1 Лап»(от Яевгсб 2)вез (77))еу, 1992), гла- ва 2. Впоследствии Люком Девроем и Брюсом Ридом (Вгпсе Веег!) (ЯСОМР 24 (1995), 1157 — 1162) был найден попахивающий шаманством резульлат — они доказали, что средняя высота равна и!пп+ 0(!об!ойп) с дисперсией 0(1об 1обп)з, где и = 1/Т(1/2е) 4.3110704070010050350470760964468902783916-, а Т(з) = 2 „, и" 'хв/и! представляет собой функцию дерева РАЗДЕЛ 6.2.3 1.
При преобразованиях должен сохраняться симметричный порядок узлов; в противном случае получить бинарное дерево поиска невозможна. 2. 5(5! = 0 только в том случае, когда 5 указывает на корень дерева (на шагах АЗ и А4 значение 5 не изменялось) и все узлы от 5 до точки вставки сбалансированы.
3. Обозначим через рл наиболыпее возможное отношение числа. несбалансированных узлов к общему количеству узлов в сбалансированном дереве высотой И Тогда рь = О, рг = з> рз = з Докажем, что рл = (Гл-~~ — 1)/(Гл+з — 1). Пусть Тл — дерево, которое максимизнрует значение рь, тогда можно предположить, что его левое поддерева имеет высоту И вЂ” 1, а правое — высоту Ь вЂ” 2 (так как, если бы оба поддерева имели высоту И вЂ” 1, интересуюп!ее нас отношение было бы меныпе, чем рл ь).
Следовательно, это отношение для Тл не превышает (рь ~Х~ Ирь гЮ, + 1)/(ьЬ+Л„+Ц, где (Ха !У ) — количество узлов в (левом, правом) поддереве. Приведенное вырюкение принимает максимальное значение при минимальных значениях (Ап А',). Значит, Тл представляет собой дерево Фнбоначчи н согласно упр. 1.2.8 — 28 рь < 4 — 1. 4. При Ь = 7 дерево имеет ббльшую длину пути. (Примечание. В работе С. С.
Розсег, Ргос. АСМ лай Сопй 20 (1965), 197-198, приведена некорректная процедура построения Х-узловых сбалансированных деревьев с максимальной длиной пути. Эдвард Лагг (Епзгага 1 о88) обнаружил, что на рнс. 3 у Фостера дан неоптимальный результат после 24 шагов (узел 22 может быть перемещен за узел 25Ц Дерево Фибоначчи порядка И, однако, минимизирует значение (И+ а) 7г' — (длина внешнего пути(Т)) по всем сбалансированным деревьям Т высотой И вЂ” 1 дчя любой неотргщательной константы а (это утверждение легко доказывается с помощью индукции по И).
Длина его внешнего пути равна ~ИГл-~ + л(И вЂ” 1)Гл = (4/лгб) ИГл~.~ + 0(Глл~) = !З(Ие! )- Следовательно, длина пути любого А!-узлового сбалансированного дерева не превышает ш!п(И!г' — 5)(Иь! ) + 0(Х)) ( А!!ойе Ж вЂ” Аг!обе !обе Ю+ 0(Х). л Более того, если )г' велико и Ь = (!8 Х), И = (Ь/ !8 й — !обе Ь) = !обе Ж вЂ” !обе !абь Х+ 0(1), можно построить сбалансированное дерево с длиной пути И7г'+ О(Ж) следующим образом: запишем %+1 = Гл+Гл — ь+ +Глы+!9' = Гь+* — Гь>ь-лХ' и построим бинарное дерево с йн узлами; затем последовательно объединим его с деревьями Фибоначчи порядков Ь, )с + 1, ..., Ь вЂ” 1 [см.
В. К!е!п апг! Р. 1ггооб, ТЬеогейса! Сошр. Ясс 72 (1990), 251 264). б. Это утверждение мажет быть доказано по индукции. Если Тл обозначает построенное дерево, имеем при 2" < ЬТ < 2" +2" п н2" +2" '<)У<2"~' рн 6. Козффициент при -" в сВ,(с)Вл(х) представляет собой число бинарных деревьев с и узлами, левое поддерево которых сбалансиравшга и имеет высоту /, а сбалансированное правое поддерево имеет высоту й. 7. С ьс = С~ + 2В„сВ„~, .следовательно, если положить пр = 1п2, ас — — О, а +з = 1п(1+ 2В шВ /С„~се) = 0(1/В„Слсз) и 6 = ехр(аа/2+ж/4+аз/8+ . ), то можно найти, что О < рш — С = С„(ехР(сс„/2 + а,ьл/4+ ) — 1) < 1, т. е. С„= )6'").
Обобщение результатов для двойных экспоненциальных последовательностей приводится в Р!Ьаласс) Опагсег!у 11 (1973), 429-437. Выражение для 6 быстро сходится к значению 6 = 1.43687 28483 94461 87580 04279 84335 54862 92481+. 8. Пусть Ьл = Вл(1)/Вл(1) + 1 и пусть сл = 2ВлВл ~(Ьл — Ьл ~)/Вать Тогда Ьс —— 2, Ьлал = 2Ьл — сл и сл = 0(Ьл/Вл л); следовательно, Ьл = 2" В+ гл, где В = 1 — сел — лег — = 0.7011798151 02026 339724486892779 46053 74616+ а гл = сл/2 + слтл/4 + крайне мало при больших И. (Журнал вычислительной математики и математической физики 6,2 (1966), 389-394.
Аналогичные результаты для 2-3-деревьев были получены Э. М. Рейнгольдом (Е. М. Ке)п8аМ), Р!Ь. ()аагг. 17 (1979), 151-157.) 9. Эндрю Одлыжко (Лпс(гев. Об!узйо) показал, что количество сбалансированных деревьев асимптотически Равно с" /()о8 —, Гз и)/и, где с — 1.916067 и /(х) = /(х+ 1).
Та же технология применима для поиска средней высоты. (См. статью Соп8гелвпв ВшпегалВпт 42 (1984), 27-52, в которой рассмотрен также перечень 2-3-деревьев.) 10. (!лГ. Ргос. Ьесгегз 17 (1983), 17-20,) Пусть Хы, хм — узлы с заданными факторами сбалансированности В(Хл). Для построения дерева установим й с- 0 и вычислим ТВЕЕ(ао), где ТНЕЕ(йтах) представляет собой следующую рекурсивную процедуру с локальными переменными Ь, Ь~ и Ц. Установить Ь с — О, 0 с — Л; затем, пока Л < Ьтах и й < Ас, присвоить !с +- й+ 1, Ь' с- Ь-~-В(Хл), ЬЕГТ(Хл) с — Ц, 810НТ(Х„) с — ТВЕЕ(Ь'), Ь с- тах(Ь, Ь') + 1, 0 +- Хл; па окончании работы вернуть О.
(Дерево 0 имеет высоту Ь и соответствует факторам сбалансированности, которые были прочитаны г момента входа в процедуру.) Алгоритм работает, даже если )В(Хл)) > 1. 11. Ясно, что при и > 2 илсеется столько же узлов +А, сколько узлов — В и +-В, и между "+л и "-" существует симметрия Егчи имеется М узлов типа+А илн -А, рассмотрение всех возможных случаев для п > 1 поктзывает, что следующая случайная вставка с вероятностью ЗМ/(и+ 1) приводит к уменьшению количества таких узлов на 1, а с вероятностью 1 — ЗМ/(п + 1) — к увеличению их количества на 1. Отсюда лсажна получить требуемый результат.
(5ТСОМР 8 (1979), ЗЗ вЂ” 41; Курт Мельхорн (Кпгс МеЫЬогп) распространил анализ на случаи удаления из сбалансированных деревьев в работе ПСОМР 11 (1982), 748 — 780 См. также работу К. А. Васса-Уаст, Сотрастб Биглтуз 27 (1995), 109-119, в кт торой приводится сводка последних разработок в области такого анализа с использованием методов, проиллюстрированных в упр. 6.2.4-8.] 12. Максимально возможное время достигается при вставке во второй внешний узел (12): С = 4, С1 = 3, П = 3, й = С2 = Г = С1 = Н1 = П1 = 1, и общее время равно 132и.
Минимум достигается прн вставке в третий от конца внешний узел (13); С = 2, С1 = С2 = 1, 11 = 2, и общее время равно 61и. (Соответствующие параметры программы 6.2.2Т равны 74и и 26и.) 13. При изменениях дерева должны обновляться только О(!ойдо) значений ЕАИК; "упро- щеннав" система может потребовать большего количества изменений.
14. Да (хотя типичные операции нед списками весьма неслучайны и вероятность появле- ния вырожденных деревьев достаточно высока). 16. Воспользуйтесь алгоритмом 6.2.2Т с установкой т < — 0 на шаге Т1 и т е- т+ КАКЕ(Р) прн К > КЕУ(Р) на шаге Т2. 16. Удалим Е, выполним ребаланснровку (случай 3) в О. Удалим Рб заменим Р на 6; выполним ребалансировку (случай 2) в Н; откорректируем фактор сбалансированности в К. 17.
(а) 19. (Решение Кларка Крейна (С!ах)г Стане).) Имеется один случай, который не может быть сведен к однократному или двукратному повороту в корне. В этом случае следует заменить на а зятем избавиться от несбалансированности с помощью однократного или двукратного поворота в С. 20. Очень сложно вставить новый узел в крайнюю слева позицию показанного дерева: однако К.-Ю. Ряйхя (К.-О.
Вайа) и С. Г. Цвебен (Б. Н. Евтбеп) разработали алгоритм вставки, который требует 0(!об 0!) шагов (САСМ 22 (1979), 508-512). 21. Алгоритм А выполняет задание за ЛГ!об !У шагов (см. упр. 5): описанный далее алто. ритм создает такое же дерево за 0(Х) шагов при помощи интересной итеративной реализации рекурсивного метода. Мы используем три вспомогательных списка. Оп,..,0~ (бинарный счетчик, который управляет рекурсией): ум ..,, у~ (список указателей на стыковочные узлы); Тм..., Т~ (список указателей на деревья). Здесь ! = ) (В(Лг+ 1)~!. Для удобства алгоритм также устанавливает Оо +- 1, уе +- л+~ + — Л.
С1. (Инициализация.) Установить 1+- О, уо +- 2~ +- Л, Оо +- 1 С2. (Получить следующий элемент.) Пусть Р указывает на следующий входящий узел (для его получения может попользоваться другая программа). Если новых узлов больше нет, переходим к шагу С5. В противном случае установить й е — 1, О е- Л и заменить Р ь+ Уь СЗ. (Продолжение.) Если й ) ! (или, что то же самое, Р = Л), установить ! +- 1+ 1, Оь +- 1, Ть +- Я, уь+~ е- Л и вернуться к шагу С2. В противном случае установить Оь э — 1 — Оь, заменить Я ьь Тю Р ь+ уз+~ и увеличить 1 на 1. Если теперь Оь ~ = О, повторить этот шаг. С4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
