Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 103
Текст из файла (страница 103)
Ташап, Х СошЬ(пагойа) ТЛеогу 2 (1967), 215-242, 4 (1968), 201; С. Сгеепе, Еигор. з. СошЬшаголсз 9 (1988). 225-240; 1), 1). 31еасог, В. Е. Тщ)ап, апб %. Р. ТЬптя(оп, Х Ашег. Ма(Л. Яос. 1 (1988), 647-681; 3. М. Райо„ТЬеогейса) 1пйгшаг)сз апс( Арр!(с. 27 (1993), 341-348; ЬЬ К. Веппеш апд О. В1гИЬоЯ„А)бебга Упгкегяайв 32 (1994), 115-144; Р. Н, Еде!глап апг) 'ъг. Вынет, МасЛщпаййа 43 (1996), 127-154. 33. Во-первых, можно свести объем памяти к одному биту А(Р) в каждом узле Р, такому, что В(Р) = А(ВЬ1ВК(Р)) — А(ЬЫМК(Р)), когда ШИК(Р) и ВИКК(Р) ненулевые; в противном случае В(Р) уже известно. Во-вторых, можно положить.
что А(Р) = О, когда 1Л.1МК(Р) и ВЬ1ИК(Р) нулевые. Тогда А(Р) может быть удален во всех др)тих узлах после обмена ЬЬ1ИК(Р) с ВЬ1МК(Р) при А(Р) = 1; сравнением КЕУ(Р) с КЕУ(ЫЬ1ЫК(Р)) нли КЕТ(ВХ,1ИК(Р)) определяется А (Р) . Естественно, на машинах, указатели которых всегда четны, каждый узел имеет два неиспользуемых бита. Чтобы получить дополнительную зкономию памяти, следует поступить, как в упр. 2.3,1-37. РАЗДЕЛ б.2.6 1. Разделяются два узла: 2. Измененные узлы: (Конечно, В'-дерево могло бы и не яметь узлов с тремя ключами, хотя на рис.
30 они показаны.) 3. (а) 1+ 2 50+ 2 51 50+ 2 51 51 50 = 2 51 — 1 = 265301. (Ъ) 1+2 50+(2 51 100 — 100)+((2 51 101 — 100) 100 — 100) = 101 = 1030301, (с) 1+2 66+(2.67 66+2)+(2 67 67 66+2.67) =601661. (Ыеныпе, чем(Ь)!) 4. Перед разделением некорневого узла убедитесь, что он имеет два заполненных соседа. Затем разделите зти три узла на четыре. Корень должен разделяться только тогда, когда в нем содержится больше 3 1(3ш — 3)/4) ключей. 5.
Интерпретация 1, попытка максимизировать сформулированную задачу дает 450. (Наихудшая ситуация возникает при наличии 1 005 символов и передаваемого родительскому узлу ключа длиной 50: 445 символов + указатель + 50-символьный ключ + указатель + 50-символьный ключ + указатель + 445 символов.) Интерпретация 2, попытка уравнять количество ключей после разделения для поддержания высокого ветвления: 155 (15 коротких ключей, за которыми следуют 16 длинных). См. Е. М.
уйсСгелбЫ, САСМ 20 (1977), 670-674. 6. Если удаляемый ключ находится не на уровне 1-1, замените его ключом-наследником и удалите последний. Для удаления ключа на уровне 1 — 1 достаточно просто стереть его; если при этом узел окажетск слишком пустым, обратитесь к его правому (или левому) соседу и выполните "вливание", т. е. переместите ключи в узел из соседа таким образом, чтобы в обоих узлах содержалось примерно одинаковое количество данных.
Такая операция невозможна только при малой заполненности соседа; в этом же случае можно обьединить два узла в один (вместе с одним ключом из родительского узла). Такое объединение можец в свою очередь, вызвать необходимость вливании иа уровне родительского узла и т. д. При наличии ключей переменной длины, как в упр. 5, может потребоваться разделение родительского узла (когда один из его ключей становится длиннее). 8.
Имея дерево Т с уг' внутренними узлами, обозначим через вью внешние узлы, тре- О) бующие й обращений, родительские узлы козорых относятся к страницам, содержащим У ключей. Пусть также А(')(в) является соответствующей производящей функцией Тогда А(')(1) + . + А(м)(1) = Х+ 1. (Заметим, что аь кратно ) + 1 при 1 < у < М.) Следующая случайная вставка приводит к появлению Я+ 1 равновероятного дерева, производящие (11 функции которых получаются путем уменьшения некоторых коэффициентов а(' на /+ 1 и прибавления )+2 к а(' (или, если,) ш М, уменыпения некоторых а( на 1 н прибавления 0+1) (м) 2 к а +,). Теперь В„, (з) равно (Я+ 1) ', умноженному на сумму производящих функций (1) 0) А(э)(з) для 7, умноженных на вероятность появления Т по всем деревьям 7'.
Отсюда следуют такие сформулированные рекуррентные соотношения: (В'."( ),",В' )( ))'= ( + ( + ) '~ ( ))(В(",( ),"-,В,'"',( ))" = ди(И (в))(0,...,О, 1)г, где Значит, Сл ш (1,...,1)(Вл() (1),...,Вь~. ) (1)) м 2В~л,(1)/(Дг+1) +Си ( = 2/н(Иг)мм, где /„(к) = д„1(я)/(и+1)+ +де(х)/2 = (дв(х)-1)/я и И' = И'(1). (Индекс ММ означает нижний левый угол матрицы.) Теперь И' = Я ) (йвб (Лм, Лм) Я для некоторой матрицы Я, где сйвб (Л),..., Лм) обозначает диагональную матрицу, элементами которой являются корни полинома )((Л) = (Л + 2)...
(Л+ М + 1) — (М + 1)!. (Все корни различны, поскольку ~(Л) = Л (Л) = 0 приводит к 1/(Л+2)+ - - + 1/(Л+М+1) = 0; это может выполняться только тогда, когда Л действительно и -М-1 < Л < -2, откуда вытекает что )Л+2!... )Л+М+1) < (М + Ц1, а зто противоречит начальному условию.) Если р(в) — некоторый полипом„ то р(И ) = р(я ~ ц(аб(Лм...,Лм)о) = 3 (бсаб(р(Лс),...,Р(Лм))я; следовательно, правый нижияйзлементр(И~)имеетвидсср(Лс)+ .+сыр(Лм),гденекоторыеконстантысс,...,см ие зависят от р.
Эти константы можно вычислить, положив р(Л) = А(Л)/(Л вЂ” Л„), так как (Иь) мм = ( — 2)ь при 0 < й < М-1, имеем р(И ) мы = р( — 2) ж (М+1)!/(Лз+2) = с р(Л1) = с А'(Лс) =с,(М+1)1(1/(Л +2)+ +1/(Л +М+1)). Значит,с =(Аз+2) '(1/(Лз+2)+ .+1/(Аз+ М+1)) '. Это дает точную" формулу Сь ~ 2™, 2с;/л(Л,); остается только исгледовать корни Лр Заметим, что )Лз + М + Ц < М + 1 для всех у, иначе мы бы имели )Л1 + 2)... )Л„+ М + Ц > (М + 1)!. Взив Лс = О, убеждаемсЯ, что 4?(Л,) < О дли 2 < 2 < М.
Согласно 1,2.5-(15) у„(х) (и+ 1)*/Г(я+ 2) при и -1 оо; следовательно, 9„(Л1) -+ О для 2 < у < М. Таким образом, Су' - -2сс/л(0) + О(1) = Нл/(Нмтс — 1) + О(1). Примечание. Приведенный анализ применим также к алгоритму простой сортировки, вкратце обсуждавшемуся в разделе 5.2.2. Вычисления могут быть легко дополнены для того, чтобы показать, что ВЦ1(1) (Нм+, — 1) '/(у+ 2) при 1 < / < Ми Вь (1) (Нмас -1) '/2.
Поэтому общее количество внутренних узлов в незаполненных страницах приблизительно равно ( ° .'. ) 3 х 2 4 х 3 (М+1) х М/Ни+с — 1 1 (М+1)(Нм+с — 1)l а общее количество использованных страниц примерно равно 1 1 1 1 Ж 1'т' — + — + + + 3 х 2 4 х 3 (М+ 1) х М М+ 1) Ни+с — 1 2(Нм+с — 1) откуда слесбчт, что асимптотическое использование памяти равно 2(Нмм — 1)/М Этот анализ был развит в работе Махмуда (МаЬшопг() и Питтеля (Рсссе!) [Х А?бог 2Ьпщ 10 (1989), 52-75), которые открыли, что дисперсия количества использованной памяти подвергается неожиданному фазовому переходу; при М < 25 дисперсия равна В(Х), ио при М > 26 оиа асимптотически равна /(Ж) )т'+~", где /(е "~~Я) = /(Н), если — -„+ а+ >31 и — 1 + а —;31 являются ненулевыми кориямя Л, с наибольшей действительной частью. Высота таких деревьев проанализирована в работах 1. Ветгоуе, Валгсош Ясгпсспгев влс( А!бощзйшз 1 (1990), 191-203, и В.
РИСе1, Влас?ош Бсгвсгшев апс1 А1богйАлж 5 (1994), 337-347. 9. Да; например, мы могли бы заменить каждое К, в (1) иа 1 плюс число ключей в поддеревьях Ро,..., Р; ь Соответствующим образом изменяются алгоритмы поиска, вставки и удаления. 10. Краткий набросок: расширим страничную схему так, чтобы исключительный доступ к буферам предоставлялся только одному пользователю одгювремеиио. Алгоритмы поиска, вставки и удаления должны быть тщательно модифицированы, чтобы такой исключительный доступ предоставлялся талько иа ограниченное время, только при крайней необходимости и таким образом, чтобы не возникало клинчей.
За подробностями обратитесь к работам В. Заспаб(, 1пб Ргос, бессесз 5 (1976), 107-112; В. Вауег апд М. БсЬЬо!п(сЬ, Асса 1пб 9 (1977), 1-21; с'. Забст, Х Ссвпр. Яувс. 5Ы 33 (1986), 275-296. РАЗДЕЛ 6.3 1. Отблески. (Па самом деле перед нами непереводимая игра слов, основанная иа близости слов С ее и СПе. В связи с зтим ниже приводится текст оригинала упражнения и ответа к нему, — Прим.
перев. Н а сгее Ьез 1еатев, мЬас боев а спе Ьате? 1летев (сЬе р)пга) о( "11еГ).) 2. Выполпнтг элгор»тм Т, яспользуя в качестве аргумента новый ключ; попок закончится неудачно на шаге ТЗ илн Т4. Если последний шаг — ТЗ, просто поместите К в элемент таблицы ЖВЕ(Р) с номером Ь н завершите работу алгоритма. В противном случае поместите в зту позицию адрес нового узла Я ~- ИЧИ1., содержащего пустые ссылки, а затем установите Р е- Ц.
Теперь присвойте Ь н Ь' соответственно следующие символы К н Х: если Ь Р Ь', сохраните К в позиции й узла 9003(Р), в Х вЂ” в позиции Ь'; однако, есля Ь = Ь', поместите в позицию Ь указатель на новый узел Я с ЗЧШ и присвойте Р е — Ц.
Повторяйте этот процесс до тех пор, кока не получится Ь ф Ь' (счнтается, что ни один нз ключей не служит началом другому). 3. Заменим ключ пустой ссылкой в том узле, в котором он находился. Если теперь данный узел стал "бесполезным" в силу того, что все его элементы, кроме одного, представляющего ключ Х, пусты, удалим этот узел н заменим соответствующий указатель в родительском узле указателем Х Еслн "бесполезным" становится родительский узел, удалим его описанным способом, 4.
Успешный поиск будет проходить так же, как и в случае несжатой таблицы, однако для неудачного поиска в сжатой таблице может потребоваться несколько дополнительных итераций. Например, такой аргумент поиска, как ТЗЗЗЗ, заставят программу произвести пмстяь итераций (что явно болыпе пяти!); этот случай является наихудшим. Необходимо также проверить невозможность зацикливания на пустых позициях. (Этот замечательный пример упаковки таблицы в 49 элементов предложен Дж. С.
Фншберном (3. Ясое РЫЬЬпгп), который также доказал, что 43 позиций для упаковки таблицы недостаточно.) Более медленоый, но болея многосторонний путь экономия памяти для луча был предложен Куртом Мази (Ките Ма!у), САСМ 19 (1976), 409-415. В общем, если нужно акать п разреженных таблиц, содержащих соответственно ям ..., я„ненулевых элементов, метод "первый подходвщнй", который смещает 1-ю таблицу на минимальную величину г, с целью избеяапня конфликтов с ранее размещенными таблицамн даст г, < (Я~ + . + хз-~)кы посколькУ каждый пРедшествУющнй ненУлееой элемент может блокировать не более яз смещений. Такая оценка наихудшего случая дает г; < 93 для табл. 1, гарантируя, что любые 12 таблиц длиной 30, содержшцне соответственно 10, 3, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2 ненулевых элементов, могут быть упакованы в 93 + 30 последовательных позиций безотносительно к лвончному представлению ненулевых элементов. Дальнейшее усовершенствование этого метода было проведено в работе В.
Е. Трап апс! А. С. Уао, САСМ 22 (1979), 606-611. Динамическая реализация сжатых лучей, прядя~ желная Ф. М. Лиангом (г. М. 1лвлб), исповьзована в таблицах переносов в издательской системе 'ХЕХ (см, П. Е. КппсЬ, САСМ 29 (1966), 471-478! Бйегаее Ргобгашпнпб (1991), 206-233). б. В каждом семействе сначала проверяется наиболее вероятный исход; для этого буквы располагаются слева направо в порядке уменьшения вероятности. Оптимальность такого упорядочения может быть доказана аналогично теореме 6.1Я.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
