Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 100
Текст из файла (страница 100)
На шаге Тб установите ВТВО(О) е- 1, Кроме тога, при вставке влево установите ю.Хик(О) +- Р, при вставке вправо установите ВХ.1КК(Ц) ь- $и.1ИВ(Р) и Втйй(Р) ь- О. На шаге Т4 измените проверку»81,1ИК(Р) ф Л" на "ВТВО(Р) ~ О". (Если узлы вспьвляются в последовательные ячейки памяти О и если все удаления осуществляются по принципу 1ЛгО (»последним вошел — первым вышел"'), поля ВТВО могут быть удалены, поскольку ВТВО(Р) будет равно 1 тогда н только тогда, когда Ы.1ИК(Р) < Р.
Подобное примечание справедзиво и длн левой, и для правой прошивок,) 3. Можно заменить А корректным алресом и установить КЕ1(А) +- К в начале работы алгоритма. В тиком случае проверки ШИК и ВЬ1ИК = А могут быть удалены из внутреннего цикла. Однако для корректного выполнения вставки необходимо ввести другой указатель, следующий за Р. Это можно сделать, дублирован код так же, как и а программе 6.2.1Р. работа программы при этом не замедляется. Время работы такой модифицированной програмллы уменьшается до 6.5С единиц. 10. Например, каждое слово х ключа можно заменить словом ах шос) пэ, где т — размер машинного слова, а а — случайный множитель, взаимно простой с пь Можно также порекомендовать величину, близкую к (4) — 1)т (см.
раздел 6.4). Гибкое распределение памяти пря работе с деревьями может сделать такие методы более прнтяпкгельными, юм схемы с хешированием. 11. )Ээ' — 2; однако зто происходит с вероятностью 1/(ЛГ Лп) только прн удалении О) НЛ'-1 ... 2. 12.
-(тэ + 1)(я + 2) удалений в доказательстве теоремы Н относятся к случаю 1, так что ответ — (Лэ + 1)/2Ж 13. Да. Доказательство теоремы Н показывает, что если удалить 1-й вставленный элемент, то для любого фиксированного )г результат будет случайным, (Г, Д, Кнехт (Р)э. )). 1)эшэз, Бзап(оЫ, 1975) показал, что результат остается случайным после любой фиксированной последовательности вставок и удалений злементов (Йэ,..., Йа).) 14.
Пусть МОЬЕ(Т) находится на уровне й н пусть Ы 1ИК(Т) = Л, ВЫИК(Т) = Вэ, 111ИК(йэ ) = Вм..., Ы.ТИК(йа) = Л, где Ва ~ Л и г( > 1. Допустим, что в правом полдереве узла МОЬЕ(йэ) находится пц 1 < э < э(, внутренних узлов. При наличии шага 1)11э длина внутреннего пути уменьшается на В+ гэ+ пэ + + пш без етого шага она уменьшается на Й+ 4+ па. 16. 11, 13, 25, 11, 12. (Если аэ является наименьшим, средним, наибольшим нз (аэ, ам аз), после удаления дерево ~' будет получено (4,2,3) х 4 раз.) 16. Да; коммутативной будет даже операция удаленшг нз перестановок, определенная в доказательстве теоремы Н (если пренебречь перенумерацней).
При наличии клемента между злементамн Х и У колэмутатнвность удаления очевидна, поскольку иа операцию удаления влияет только относительное расположение злементов Х, У и нх наследников и удаления Х и У не взаимодействуют между собой. С другой стороны, если У является преемником Х и У вЂ” больший елемент, то оба порядка удаления просто удаляют злементы Х и У. Ясля У вЂ” преемник Х, а Я вЂ” преемник У, оба удаления приведут к замещению первого встреченного злемента Х, У или Е злементом Я и к удалению второго н третьего из встретившихся злементов нз перестановки.
16. Воспользуйтесь упр. 1.2.7-14. 19. 2Нл — 1 — 2~~~ э( — 1)~/ЙЛэе = 2Нл — 1 — 2/6+ О(ээг ~). (Распределение Парето 6.1-(13) приводит к подобному асимптотическому результату с поправкой О(п ~ )оК и).) 20. Да„конечно. Предположим, что Кэ « . Кю так что дерево, построенное при помощи алгоритма Т, амрожденное. Если, например, ра = (1+((Лэ+ 1)/2- В) е)/Лэ, среднее число сравнений равно (Лэ+ 1)/2 — (Лгэ -1) е/12, в то время как оптимальное дерево требует менее [!бээг) сравнений, 21.
1, у, ц, зо, з. (Большинство ) гдов равны 30', 66' нлн 90'.) 22. При э( = 2 зто очевидно; при г( > 2 имеем г[э, 2-1) < г[4+1, /-1] < г[э+1, Я. 23, (Увеличение веса первого узла в конце концов приведет к его перемещению в корневое по- ложение. Это наводит на мысль о сложности динамического поддержания оптимальности дерева.) 24. Пусть с означает пену дерева, полученного посредством удалении и-го узла из опти- мального дерева.
Тогда с(0, и — Ц < с < с(0, и) -«„», поскольку операция удаления всегда перемещает (и-1) на один уровень вверх, Аналогично с(0, и) < с(0, и-1) + «„-», так как при предлатаемой замене цена дерева равна последнему выражению, откуда следует, что с(О, и-1) = с = с(О,и) — «„ 25. (а) Предположим, что А < В и В < С, и пусть о б А, Ь б В, об С, с < о. Если с < Ь, то с б В; следовательно, с б А и а б В; значит, а 6 С. Если с > Ь, то а б В; следовательно, а б С и с б В; значит, с б А. (Ь) Это легко доказать самостоятельно.
20. Цена любого дерева имеет вид р + 1х, где у > 0 — некоторое действительное число, а 1 — целоо, большее О. Минимум конечного числа таких функций (взятых по всем деревьям) всегда имеет описанный вид, 27. (а) Из ответа к упр. 24 (в частности, из того, что с = с(0, и — 1)) вытекает, что Н(0, и — 1) = Н(0, и) ~ (и). Ь) Если 1 = 1', результат а указании тривиален. В противном случае обозначим пути к и как Я,Я,...,И и Я,Я,...,Я. Поскольку г = ге > ее = в и гг < сч - -и, можно найти уровень Ь > О, такой, что гл > ел и гл»; < ельь По индукции имеем г»+» б Н(г»,и), ел»» б Н(в»,и) н Н(ел, и) < Н(г», и).
Значит, г»+» б Н(е*, и) н е»+~ б Н(г», и); отсюда следует результат, приведенный в указании. Теперь для долазательства того, что Нл < Нл, положим, что г б Н'„, е б Нл, з < г, и рассмотрим оптимальнме деревья, показанные для х = хл. Получим, что 1 > 1», и можно предположить, что 1' = 1». Для доказательства соотношения Нл < Нл„ы положим, что г б Нл, е б Нл,, з < г, и рассмотрим оптимальные деревья, показанные для х = хл»ь Получим, что 1' < !л, и можно предположить, что 1 = 1л. 29. Это вырожденное дерево (см. упр, 5) с 700 на вершине дерева и ТОН внизу, которое требует в среднем 19.158 сравнений. Дугтас А, Гамильтон (Вопй!аз А.
На»и!!соп) доказал, что наихудшим деревом всегда является некоторое вырожденное дерево. Таким образом, существует 0(г» ) алгоритм по- лучения наихудших бинарных деревьев поиска. ЗО. См. Е. Ь, Яешпег, 1пlогшас1ол Ргасеаппб Ъесссгз 4 (197б), 90-94; Р. Р. Уао, ЗЕАМ Х А!Небгак ап»1 Растете Мегйо»!з 3 (1982)„532-540.
31. См. Асса 1пйвтпас)са 1 (1972), 307-310. 32. Когда М достаточно велико, оптимальное дерево должно иметь указанный вид и минимальная цена должна быть в М рвз больше минимальной длины внешнего пути плюс решение сформулированной проблемы, (Првмечонис. Статья Весснера, указанная а ответе к упр. 30, поясняет, как найти оптимальное бинарное дерево поиска высоты < Ь. Для частного случая р» = — — р„= 0 решение было получено Т. Ч. Ху (Т. С.
Пи) и К. Ч. Таиом (К, С. Тап) (МЕС Верогл 11П (1)и!т. о! %'!есоае!и, 1970)). А. М. Гарсии (А. М, Сшз!а) и М. Л. Воч (М. 1.. %ЪсЬв) доказали, что в атом случае все внешние узлы окажутся максимум на двух уровнях, если ш!и»=»(«»-» + «») > п»ах~ „" е «», а также представили алгоритм, требующий только О(и) шагов для поиска оптимального двухуровневою дерева). ЗЗ.
Решение поставленной задачи можно найти в А. !сш, Б!СОМР Б (197б), 9-18; альтер- нативные варианты рассмотрены в работе 11. Зра)ег, Асса !Поггпж!са 31 (1994), 729-740. 34. Согласно аппроксимации Стирлннга прн р«...Р„~ О зто значение равно 2««»г»"'ги !л х х (2яЛ ) 1«-"Нг(р,... Р„)-'«г(1+ О(1/Н)).
36. Минимальное значение правой части неравенства, равное 1 — р+ Н(Р, 1 — Р), достигается при 2т = (1 — р)/Р. Однако согласно (20) при й = 2 Н(р, д, г) < 1 — р+ Н(р, 1 — р). 36. Сначала докажем утверждение из указания, принадлежащее Дженсену (Лепвеп) (Ас»а Ма»!». 30 (1906), 1«5-193). Если / вогнута, следовательно„функпия д(р) = /(рх+ (1— р)у) — р/(х) — (1 — р)/(у) вогнута; кроме гого, она удовлетворяет условию д(0) = д(1) = О. Если для некоторого 0 < р < 1 д(Р) < О, то должны существовать ро < р, для которого д'(Ро) < О, и р«> р, для которого д (р«) > 0 согласно теореме о среднем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
