Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 104
Текст из файла (страница 104)
(Сьь САСМ 12 (1969), 72-76.] У 0 и а $ м й $ й Я И й Я й " Ц и 3 й 5 й й й й и 3 5 У 3 и 3 -В ЮЪ Т. Например, 6, 4, 1, 2, 3, 5, 6, 7, 12, 9, 10, 11, 13, 14, 15. (Независимо от того, какая последовательность используется, ии левое, ни правое поддерево не может содержать больше двух узлов на уровне 4,) Даже получеяное нами "наихудшее" дерево принадлежит к числу четырех наилучших возможных деревьев, так что, как видите, деревья цифрового поиска не слишком чувствительны к порядку вставки. 6. Да. В ноле КЕТ теперь содержится только усеченный ключ; левые биты, значения которых определяютск позицией узла„удалены.
Анвлогичнан модификация применима и к алгоритму Т, 9. ЗТАЕТ ЫХ К эхе. м~лио. [ х и ЫП ВООТ 1 Р +- ЕООТ. (гП ш Р) Л(Р 2Р 1 4Н Ы2 0,1(З1 ТИК) С2 4. и .иие вп . Н+- ЕЕХИК(Р). )22 ЗР С2 Переход к шагу О5 при Я = Л. 1Н ЕИТ1 0,2 С вЂ” 1 Р+- О. 2Н СИРХ 1,1 С ДЗ, ~~венские. )Е ЗОССЕЗЗ С Выход кри К = КЕТ(Р). ЗЬВ С вЂ” Я Смещение К влево на один бит. 2АО 4В С вЂ” Ь' Переход к шагу П4, если вмделенный бит равен 1. 102 0,1((Л1ИК) С1 . П ме влево 9+- 1Д.ХИК(Р).
12ИХ 1В С1 Переход к пшгу ))2 с Р е- О, если 0 Тэ Л. ЗН Продолжение то же, что н в программе 6.2.2Т, с обменом местами гА и гХ. $ Время работы фазы поиска этой программы равно (10С вЂ” 35+ 4)к, где С вЂ” Я предспь алвес собой число проверок битов. Для случайных данных приближенное среднее время работы таково. Неудачно Программа 6.2.2Т 15 !и )Т вЂ” 2.34 Даннан программа 14,4!и Ф + 1.26 (Следовательно, при не очень больших Ю программа 6.2.2Т работает несколько быстрее.) 10. Обозначим черну 6) операцию "исключыошее или" над и-битовыми числами, и пусть у(х) = и — (!6(х + 1) ( — число левых ненулевых битов х.
Вот одно из решений; (Ь) если поиск с помощью алгоритма Т заканчивается неудачно на шаге ТЗ, то й на единипу меньше количества проверенных битов; в противном случае, если поиск заканчивается на шаге Т4, А = у(К сэ Х), (а, с) Выполним обычный поиск, но при этом будем хранить х— минимальное значение Кеэ НЕТ(Р) по всем КЕТ(Р), сравнивавшимся с К в процессе поиска. Тогда А = у(х). (Докажите, что наибольшее число битов, совпадающих с К, имеют ключи, сравниваемые с аргументом. В случае (а) максимум Й достигеетгл либо для наибольшего ключа < К, либо для ншьченьшего ключа > К.) 11.
Нет; удаление узла только с одним пустым поддеревом приведет к потере одного бита в ключах непустого поддерева. Для удаления узла следует заменить его одним из его терминальнмк наследников, например, по возможности двигаясь при поиске только вправо. 12. Вставим три случайных числа — а, )Т, Т из диапазона (О, 1) — в изначально пустое дерево; затем удалим а с вероятностью р,,9 с яероятностью д, Т с вероятностью г с помощью предложенного в предыдущем упражнении аягоритма.
Дерево !юлучается с вероятностью Тр+ ХС+ -г, а это равно — только при р ш О, ! ! ! ! 13. Добавить к каждому узлу поле КЕТ и сравнивать К с этим ключом перед проверкой элемента вектора иа шаге ТХ. Табл. 1 должна быть изменена следующим образом: узлы (1),, (12) долхгны содержать ключи ТНЕ, АИО, ВЕ, РОВ, НТБ, 1И, ОР, ТО, И1ТН, НАТЕ, НЕ, ТНАТ соответственно (если они астввляются в порядке уменьшения частрты), и эти ключи должны быть удалены из своих прежних позиций. (Соответствующая программа будет медленнее и сложнее программы Т. Более прямолинейное М-арное обобщение алгоритма П привело бы к созданию дерева с !!! узлами с одним ключом и М ссылками в каждом узле.) 14.
Если) ( и, то имеется только одко такое место, а именно — КЕТ(Р), Однако при!' > и множество всех появлений находится посредством обхода поддерева узла Р; если имеется г появлений К в ТЕХТ, то поддерево содержит г — 1 узел (включая узел Р) н, таким образом, имеет г полей ссылок с ТАС = 1, Эти поля ссылок указывают на все узлы, ссылающиеся на позиции в ТЕХТ, которые содержат К (в повторных проверках ТЕХТ нет необходимости) . 16, Начните построение дерева с установки КЕТ(НЕАО) равной первой ссылке иа ТЕХТ, а также 14.1ИК(НКАО) +- НЕАО, 1.ТАС(НКАО) +- 1. Дальнейшие ссылки иа ТЕХТ могут быть вставлены в дерево с использованием следующего алгоритма. Установить К равным значению нового ключа, который следует вставить (это первая ссылка на массив ТЕХТ, которую делает алгоритм).
Выполните алгоритм Р. Он должен закончиться неудачно, поскольку нн один ключ не может быть префиксом другого ю!юча. (На шаге Рб осуществляется вторая (н последняя) ссылка на массив ТЕХТ, больше ссылки на ТЕХТ делаться не будут). Предположим теперь, что ключ, найденный на шаге Рб, сот:!всуется с аргументом К по первым ! бит, но отличается, начиная с позиции ! + 1 (в которой К им!мт цифру Ь„а ключ соответственно цифру 1-6). (Хотя при поиске с помощью алгоритма Р ключ ! может стать намного больше„чем 1, можно доказать„что описанная здесь процедура найдет наилучшее совпадение с К среди ессх имеющихся ключей.
Таким образом, во всех ключах текста, которые совпадают с К по первым ! бит, в качестве (!+1)-го бита содержится 1 — 6.) Теперь повторим выполнение алгоритма Р, в котором К заменено его ведущими ! бит (т. е. и +- !). На этот раз поиск будет успешным, поэтому шаг Рб ВЫПОЛНЯТЬСЯ НЕ бУДЕт. Уетаиаантс В «и АТАПч КЕТ(В) Е- ПОЛОЖЕНИЕ НОВОГО КЛЮЧа В ТЕХТ. Если )Л,1ИК(Ц) = Р, установите ШИК(С) +- В, ! +- ХТАС(Я), 1ТАС(Ц) <- 0; в противном случае установите В).1ИК(Я) +- В, ! +- ВТАС(О), ВТАС(С) +- О. Если Ь = О, установите БОТАС(В) +- 1, 1Л.1ИК(В) <- В, ВТАС(В) 1- 1, В61ИК(В) +- Р; иначе установите ВТАС(В) +- 1, В1.1ИК(В) !†В, 1 ТАС(В) +- 1, Ы.1ИК(В) +- Р.
Если ! = 1, Установите БК1Р(В) Е- 1 + ! — 1; в противном случае установите БК1РВХ) <- 1 + ! — ! + БК1Р(Р) и БК1Р(Р) +- 1 — ! — 1. 1О. Структура дерева требует, чтобы в каждый узел входила одна идущая снизу пунктирная линия, которая начинается в той части дерева, где соответствующий ключ впервые отличается от всех остальных, Если такой части дерева нет, алгоритмы перестают работать.
Мы можем просто убрать ключи, служащие началом других ключей, но тогда алгоритм из упр. 14 не получит достатг иного количества данных для поиска есек вхождений аргумента, 17. Если положить ве = а~ --- О, то х„= а„+~~~ ! !( — 1) а»/(щ" ' — 1) ы ~~~ („)(-1) а»гп /(гл " — 1). »2» 16/ »2» 18. Для решения (4) необходимо преобразование а = [н> 1], а именно — а„= [и=0]— 1+ и; следовательно, для Х > 2 получим Ал = 1 — (/л + !гл, где 11л = К(Х,О,М) и 1'я = К(Ф, 1, М) (в обозначениях из упр. 19).
Аналогично для решения (б) нужно взять ах ж п — [и = 1] = а„и получить Ст = !У + гл для Ж > 2. 19. При з = 1 имеем 1г, = К(п, 1, гп) = и((!п и+ 2)/1и ш — -' — 6а(» — 1)) + О(1), а при в > 2 имеем К(п,в,т) ж (-1)'п(1/!пш+6, з(п — з))/в(э — 1)+О(1), где 6,(п) = — ~~~ 61(Г(з — 2та!г/!пят) ехр(2так!об и)) 2 1п гп »й! представляет собой периодяческую функцию от!ойп.
[В этом выводе использовался тот факт, что , гп+ вз и *+' Гчзт'" Г(з)п' ' *6з К(п+в,в,гп)/(-1)'~ ) = — / +О(ц '). з ) 2вч /,Гз ~ гп' » * — ! Для малых гп и в весьма малым являетсн 6 (см. Упр, 5.2.2-46). Обратите внимание на то, что 6,(п — а) = 6,(п) +0(п ') при фиксированном а.] 20. Для случая (а) положим а„= [п>з) = 1 — 2 "» э[и=к]; для (Ь) — а» = и— х»=о !г[п = 6]; в случае (с) требуется найти решение рекуррентного соотношения пг' " 6» („")(пз — 1)" "у» при и > з, ("") при и < з.
Подставив з„= р„-и, получим реку ррентное соотношение рассмотренной в упр. 17 формы, где а„= (1 — М ') ~ ( ) [и м Ц. » О Таким обрезом, используя обозначения из предыдуших упражнений, получаем следующие ответьи (а) 1 — К(ХО,М) + К(Ю, 1,М) — + (-1)' ~К(Ф,в, М) = Ф/(з!аМ)— !»(6-ю(/»г) + 6о(Х вЂ” 1) + А(Л вЂ” 2)/2 1 + .. + 6, и(Х вЂ” в)/е(з — 1)) + О(!); (Ь) лг '(г! + К(!У,1,М) — 2К(Д1,2,М) + ° + (-1)' 'вК(!У,з,М)) = (!пХ+ у — Н, ~)/!пМ+ 1/2— (6 (Л' — !)+А(лг — 2)/1+ . +6, (Л' — з)/(в — 1))+О(!»' '); (с) !» '(1т+(! — М ') х Я» ~(-1)~(~)К(Ж,!г,М)) = 1+-'(1 — М ')((~ — 1)/1~М+6~(Х вЂ” 2)+ .+6, ~(!у — ))+ О(Х '). 21.
Пусть всего имеется Ая узлов. Число непустых ссылок равно Ал — 1, а количество узлов без ссылок — Х, так что общее количество пустых ссылок составляет МАл— Ал + 1 — а1 Для получения среднего количества пустых ссылок в любом фиксированном узле следует разделить найденное значение на М. [Среднее значение Ая приведено в упр. 20, (а).] 22. Для каждой из М' последовательностей лидирующих битов имеется такой узел, что, по меныпей мере, два ключа начинаются с этой последовательности. Вероятность того, что с нее начинается ровно Ь ключей, составляет ~ ) М-"(! - М-')" ", ~Х~ 6) так что среднее количество узлов луча на уровне ( равно М (1-(1-М ')~)-!т(1-М ')~ ~. 23.
Рассмотрим более обшую задачу — случай для произвольного в (как в упр. 20). Если иа уровне 1 имеется ау узлов, то в них содержится асы ссылок и Ма~ — асы позиций, в которых поиск может быть неудачным. Таким образом, среднее количество проверок цифр составляет Я, о(1+1)М"' '(Ма~ — аьы) = ~,>оМ"'аь Используя формулу для а~ в случайном луче, получаем К(у+1, 1, М) — 2К(У+1,2, М)+ + (-Ц (в+1)К(Е+1, +1,М) Я+1 1пХ+7 — Н, 1 6~(Ф-1) б»(АГ-в) 1пМ 2 1 в 24.
Необходимо найти решения рекурреитпых соотношений хе = х~ = Вэ = ул и О, х =пг " ~ [ ~) ~х, + ° . ° +х„+ ~ [п1140)) ф+'"+~ \ »им,,п 1~~бт =а„+гп' "~ ~ )хы Ф» = гп ~Х' (р « +'''+Ф» + ~~~ [па РО[пу) »~.~-"+»» »им...,п» у гй »16» =5»+т "~~ ~ )рв, для и > 2, где а„= гл(1 — « — 1/еп)") и 5» ж 1(гл — 1)н(1 — « — 1/гл)" ~). Согласно упр. 17 и 18 ответы таковы: (а) хл = Х+ Ъгя — СЪ вЂ” [Аг = 1) = Аи+ Х вЂ” 1 (этот результат может быть получен непосредственно, поскольку количество узлов в лесу всегда на Ф вЂ” 1 балыке количества узлов в соответствующем луче!); (Ь) рл/Ю = -'(М вЂ” 1)1гл/Х = 1(М— 1)((1п Х+ у)/1и М вЂ” -' — д~(Ж вЂ” 1)) + О(Ф"'), 25.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
