AOP_Tom3 (1021738), страница 204

Файл №1021738 AOP_Tom3 (Полезная книжка в трёх томах) 204 страницаAOP_Tom3 (1021738) страница 2042017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 204)

(Конкатенация.) Установить 11ХИК(Р) е- Ты Ж.1ИИ(Р) +- 9, В(Р) Э- О, Ть +- Р и вернуться к шагу С2. Сб. (Завершение,) Установить 11ХИИ(уь) ь — Ть, Ы.1ИИ(уэ) +- уь и В(уь) +- 1 — Оь-~ для 1 < й < !. Алюритм завершен (у~ указывает на корень искомого дерева). З Шаг СЗ выполняется 2Л! — и(М) раз, где н()У) — число единиц в двоичном представлении числа Лг.

22. Высота взвешенно-сбалансированного дерева с Х внутренними узлами всегда лежит между (8(К+ 1) и 2 !8(Х+ 1). Для получения верхней границы заметьте, что более тяжелое поддерево корня имеет не более (Ж+ 1)/»/2 внешних узлои. 23. (а) Постройте дерево, правое поддерево которого представляет собой полное бинарное дерево с 2" — 1 узлами, а левое — дерево»рибоначчи с 5'„.»» — 1 узлами. (Ь) Постройте взвешенно-сбалансированное дерево, правое поддерево которого имеет высоту порядка 2 !8/»», а левое — порядка )8Е!» (см упр.

22). 24. Рассмотрим наименьшее дерево, удовлетворяющее условию, но не являющееся идеально сбалансированиыл», Тогда его левое и правое поддеревья идеально сбалансированы и соответственно количество их внешних узлов составляет 2 и 2, где ! ЭЬ г, что противоречит заданному условию. 26. После вставки узла в нижнюю часть дерева мы движемся вверх, проверяя весовой баланс в каждом узле на пути поиска. Предположим, что в узле А в (Ц имеется несбалансированност»ч а новый узел вставлен в правое поддерево, где В и ево полдеревья взвешенно-сбалансированы. Тогда после однократного поворота баланс восстановится, если ((и(+ !»9()/(7! >»/2+ 1, где (х! означает число внешних узлов в дереве х. Однако можно показать, что в этом случае достаточно двукратного поворота (см.

ЯСОМР 2 (1973), 33-43). 27. Иногда в узлах с двумя ключами необходимо выполнить два сравнения. Наихудший случай встречается в деревьях, подобных изображенному, когда в некоторых ситуациях требуется 2 !8(»»~ + 2) — 2 сравнений. 29. Частичное решение, прииадлев»ашее Э. Яо (А. Уао), таково; для Х > б ключей нижний уровень будет содержать в среднем 1(Л + 1) узлов с одним ключом и у»(Х+ 1) узлов — с двумя ключами.

Общее среднее количество узлов при больших Х лежит между 0.70!»Е и 0.797»». (Ас»а Ел1оппабса 9 (1978), 159-170.) 30. Для случая наилучшего подходящего упорядочите записи по размерам по произвольному правилу связывания областей с одним и тем же размером (см. упр. 2.5 — 9). В случае первого подходящего упорядочите записи по адресам с дополнительным полем в каждом узле, содержащем размер наибольшей области в поддереве, для которого данный узел является корнем. Эти поля могут обновляться при вставках и удалениях. (Впрочем, хотя время работы и оказывается равным О(!обо), вероятно, на практике метод блужданий из упр. 2.5-б будет более эффективным. Однако без 80»ЕЕй память может распределяться еще лучше, так как обычно "на всякий пожарный" поддерживаетск свободной область памяти большого объема.) В работе К. Р.

Вгеп», АС5Е Тгапэ. Ргоб. Йапбиабеэ ап»Е Був»еп»э 11 (1989), 388-403, можно ознакомиться с усовершенствованием описанного метода. 31. Используйте почти сбалансированное дерево с дополнительными связями вверх для крайней слева части и стек отложенных корректировок фактора сбалансированности вдоль этого пути (для каждой вставки требуется ограниченное число таких корректировок). Эта задача может быть обобщена на случай использования О(!об т) шагов для поиска, вставки и/или удючения элементов, которые находятся в ьч шагах от данного "указателя"; в качестве такого указателя может выступать любой узел, расположение которого известно. (См.

К Нойс(!ее!оп апб К. 1(еЬ!Ьогп, АсСа Хлб 17 (1982), 157-184.) 32. Нри каждом вращении вправо увеличивается один из гю пе изменяя остальных, откуда гь < гг, Чтобы показать, что этого достаточно, предположим, что г, = г', для 1 < )' < 1г, но гь < г'„. Тогда существует вращение вправо, при котором гь увеличивается до значения ( г'„, потому что числа г~ гв ., г„удовлетворяют условию упр. 2.3.3 -19, (а). Примечание. Этот частичный порядок, впервые введенный в 1951 году Д.

Тамарн (!). Тагпап), имеет много интересных свойств. Любые два дерева имеют наиболыпую нижнюю границу ТЛ Т', определяемую размерами правых поддеревьев пнп(г,, г,) пнп(гм гэ) . тт(г, г'„) „так же, как и нанменыпая верхняя граница Т иТ' определяется размерами левых поддеревьев т!п(1„1',) пцп(1п!в) .. т!и(1„, 1'„) Размеры левых поддеревьев, конечно, на единицу меньше, чем паля ВАМК в алгоритмах В и С. За дополнительной информацией обратитесь к работам Н. Рпейпап апб (). Татаг(, Х СоглЬ(ла(ог(а1 ТЬеогу 2 (1967), 215-242, 4 (1968), 201; С.

Сгеепе, Енгор. 1. СотЬ!ла!ог)св 9 (1988), 225 -240; П П. Б!еа!ог., К Е. Тат)ап, апб )гг'. Р. Т!гага!оп, Х Апзег. МаГЬ. Бос. 1 (1988), 647 — 681; д. М. Ра!!о, Т1~еогег(са) 1пГогглаВсв алЯ Аррбс. 27 (1993), 341 -348, М К. Веппет апд С. В!гЬЬоЯ, А18еЬга (Глл егвайв 32 (1994), 115 — 144; Р. Н. Ебе!гоап апг( У. Кетег, МвейетаН)га 43 (1996), 127-! 54. ЗЗ. Во-первых, можно свести объем памяти к одному биту А(Р) в каждом узле Р, такому, что В(Р) = А(КЬ)ИК(Р) ) — А(Е11ИК(Р)), когда ШИК(Р) н КЬ1ИК(Р) ненуловые; в противном случае В(Р) уже известно. Во-вторых, можно положить, что А(Р) = О, когда ШИК(Р) и КЬКИК(Р) нулевые.

Тогда А(Р) может быть удален во всех других узлах после обмена Ы.1МК(Р) с 81.1ИК(Р) при А(Р) = 1; сравнением КЕУ(Р) с ХЕУ(ШМК(Р)) или КЕУ(КЬ1ИК(Р)) определяется А(Р). Естественно, на машинах, указатели которых всегда четны, каждый узел имеет два неиспользуемых бита. Чтобы получить дополнительную экономию памяти, следует поступить, как в упр. 2.3 1-37. РАЗДЕЛ 6.2.4 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) 1011 1030301 (с) 1+ 2 66-(- (2 67 66+ 2) + (2 67. 67 66+ 2. 67) = 601661. (Меньше, чел» (Ь)!) 4. Перед разделением некорневого узла убедитесь, что он имеет два заполненных соседа. Затем разделите эти три узла на четыре. Корень должен разделяться только тогда, когда в нем содержится болыне 3 ((Зт — 3)/4) ключей.

5. Интерпретация 1, попытка максимизировать сформулировы»ную задачу дает 450. (Наихудшая ситуация возникает при наличии 1005 символов и передаваемого родительскому узлу ключа длиной 50: 445 символов + указатель + 50-символьный ключ + указатель + 50-символьный ключ + указатель + 445 символов.) Интерпретасщи 2, попытка уравнять количество ключей после разделения для поддержания высокого ветвления: 155 (15 коротких ключей, за которыми сяедуют 16 длинных). См. Е. М. МсСге(5Ь», САСМ 20 (1977), 670-674.

6. Егли удаляемый ключ находится не иа уровне 1 — 1, замените его ключом-нагледником и удалите последний. Для удаления ключа на уровне 1 — 1 достаточно просто стереть его; если при этом узел окажется слишком пустым, обратитесь к его правому (или левому) соседу и выполните "вливание", т. е. переместите ключи в узел из соседа таким образом, чтобы в обоих узлах содсржалось примерно одинаковое количество данных.

Такая операция невозможна только при малой заполненности соседа; в этом же случае можно объединить два узла в один (вместе с одним ключом из родительского узла). Такое объединение может, в свою очередь, вызвать необходимость вливания на уровне родительского узла и т. д.

При наличии ключей переменной длины, как в упр. 5, может потребоваться разделение родительского узла (когда один из его ключей становится длиннее). 0. Имея дерево Т с Х внутренними узлами, обозначим через а~' внешние узлы, требующие 7» обращений, родительские узлы которых относятся к страницам, содержащим 1 ключей. пусть также А~»~(г) является соответствующей производящей функцией, тогда .4(')(1) + + А(м)(1) = Х+ 1. (Заметим, что о(ь) кратно 7+ 1 при 1 < у < М) Следующая случайная вставка приводит к появлению Х+1 равновероятного дерева, производящие функции которых получаются путем уменьшения некоторых коэффициентов а11 на 1+1 и О) прибавления д 52 к а(1 ) (или, если 1' = М, уменьшения некоторых а(ь' ) на 1 и прибавления ()э1) (и) 2 к аь»1). ТепеРь Вн (з) Равно (Х+ 1), Умпоженнол»У на сУммУ пРоизводвщих фУнкций (1) (1) -1 А(1)(з) для T, умноженных на вероятность появления T по всем деревьям 7 Отсюда следуют такие сформулированные рекуррентные соотношения: (В")(,),...,В,', )( ))' = (7+ (Х+ ц-'И (з))(В(,"1(.),...,В, ')(,))' = дн((4 ( )ИО,...,0,1)~, где Значит, Сч — — (1,..., 1)(В»» (1),..., Вй '(1)) = 2В„, (1)/(Х+ 1) + С,'», — — 2/ч(И')мм, где / (з) = д 1(х)/(о+1)+ +да(х)/2 = (д„(х)-1)/х и И' = И'(1).

Характеристики

Тип файла
DJVU-файл
Размер
10,16 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6540
Авторов
на СтудИзбе
300
Средний доход
с одного платного файла
Обучение Подробнее