Главная » Просмотр файлов » Алгоритмы - построение и анализ

Алгоритмы - построение и анализ (1021735), страница 64

Файл №1021735 Алгоритмы - построение и анализ (Алгоритмы - построение и анализ) 64 страницаАлгоритмы - построение и анализ (1021735) страница 642017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

12.3-4. Предположим, что указатель на узел у бинарного дерева поиска хранится в некоторой внешней структуре данных и что предшествующий ему узел а удаляется из дерева с помощью процедуры Тквк РБ.втк Какая проблема при этом может возникнуть? Каким образом следует переписать процедуру Тквк Веьете, чтобы ее избежать? Является ли операция удаления "коммутативной*' в том смысле, что уда- ление х с последующим удалением у из бинарного дерева поиска приво- дит к тому же результирующему дереву, что и удаление у с последующим удалением х? Обоснуйте свой ответ. 12.3-5.

12.3-6. Если узел а в процедуре Тквк 1)кьктп имеет два дочерних узла, то можно воспользоваться не последующим за ним узлом, а предшествующим. Утверждается, что стратегия, которая состоит в равновероятном выборе узла). Затем в строках 4-6 х присваивается указатель на дочерний узел узла у либо значение яь, если у у нет дочерних узлов. Затем узел у убирается из дерева в строках 7 — 13 путем изменения указателей в р [у] и к.

Это удаление усложняется необходимостью корректной отработки граничных условий (когда х равно мш или когда у — корневой узел). И наконец, в строках 14-16, если удаленный узел у был следующим за а, мы перезаписываем ключ л и сопутствующие данные ключом и сопутствующими данными у. Удаленный узел у возвращается в строке 17, с тем чтобы вызывающая процедура могла при необходимости освободить или использовать занимаемую им память. Время работы описанной процедуры с деревом высотой Ь составляет О (Ь).

Таким образом, в этом разделе мы доказали следующую теорему. 328 Часть !!!. Структуры данных предшествующего или последующего узла, приводит к большей сбалансированности дерева. Каким образом следует изменить процедуру Ткее РееЕТе для реализации указанной стратегии? * 12.4 Случайное построение бинарных деревьев поиска Мы показали, что все базовые операции с бинарными деревьями поиска имеют время выполнения О (6), где 6 — высота дерева.

Однако при вставке и удалении элементов высота дерева меняется. Если, например, все элементы вставляются в дерево в строго возрастающей последовательности, то такое дерево вырождается в цепочку высоты и — 1. С другой стороны, как показано в упражнении Б.5-4, 6 > '1)кп).

Как и в случае быстрой сортировки, можно показать, что поведение алгоритма в среднем гораздо ближе к наилучшему случаю, чем к наихудшему. К сожалению, в ситуации, когда при формировании бинарного дерева поиска используются и вставки, и удаления, о средней высоте образующихся деревьев известно мало, так что мы ограничимся анализом ситуации, когда дерево строится только с использованием вставок, без удалений.

Определим случайное бинарное дерево поиска (гапдош1у Ьш!! Ь1пагу зеагсЬ !гее) с п ключами как дерево, которое возникает при вставке ключей в изначально пустое дерево в случайном порядке, когда все п! перестановок входных ключей равновероятны (в упражнении 12.4-3 требуется показать, что это условие отличается от условия равновероятности всех возможных бинарных деревьев поиска с п узлами). В данном разделе мы покажем, что математическое ожидание высоты случайного бинарного дерева поиска с п ключами равно О (!к п).

Мы считаем, что все ключи различны. Начнем с определения трех случайных величин, которые помогуг определить высотуслучайного бинарногодерева поиска. Обозначая высоту случайного бинарного дерева поиска с и ключами через Х„, определим экслоненциальиую высоту У„= 2~". При построении бинарного дерева поиска с п ключами мы выбираем один из них в качестве корня. Обозначим через В„случайную величину, равную рангу корневого ключа в множестве из всех и ключей, т.е. В содержит позицию, которую бы занимал ключ, если бы множество было отсортировано. Значение В„ с равной вероятностью может быть любым элементом множества (1,2,...,и).

Если В„= г', то левое поддерево корня представляет собой случайное бинарное дерево поиска с 1 — 1 ключами, а правое — с п — г' ключами. Поскольку высота бинарного дерева на единицу больше наибольшей из высот поддеревьев корневого узла, экспоненциальная высота бинарного дерева в два раза больше наибольшей экспоненциальной высоты поддеревьев корневого узла. Если В„= г', то У„= 2 тпах(У; ВУ„;). Глава 12. Бинарные деревья поиска 329 Очевидно, что Уз = 1„поскольку экспоненциальная высота дерева с одним узлом равна 2о = 1; кроме того, для удобства определим Уо = О. Далее мы определим индикаторные случайные величины Я„л, Я„д,..., Я„„, где Поскольку В„с равной вероятностью может быть любым элементом множества 11,2,...,п), Рг(В„= Ц = 1/и для всех 1 от!до и, а значит, согласнолемме 5.1, Е [Як,з] = 1/и (12.

1) для всех г = 1, 2,..., и. Кроме того, поскольку только одно значение Я„; равно 1, а все остальные равны О, имеем 1'„= ,'~ Я„,;(2 шахЯ ыУ„;)). з=з Е[У] = Е ,'> Я„;(2. шах(У; ыУ„;)) ~=1 (в силу линейности математи- ческого ожидания) ~~> Е[Я„;(2 щах[У; ыУ„;))] = в=1 и ~~> Е[Е„,]Е[2 шах[У; з,У„;)] = в=1 ~> — . Е [2 шах (У; ы У„;)] = 1 ~=1 (в силу независимости Я и У) (в соответствии с (12.1)) Мы покажем, что Е [У„] полиномиально зависит от и, что неизбежно приводит к выводу, что Е [Х„] = 0 (1б п). Индикаторная случайная переменная Я„; =? (В„= 1) не зависит от значений У; з и У„;. Если В„= 1, то левое поддерево, экспоненциальная высота которого равна У, з, случайным образом строится из з — 1 ключей, ранги которых меньше з. Это поддерево ничем не отличается от любого другого случайного бинарного дерева поиска из г — 1 ключей.

Выбор В„= г никак не влияет на структуру этого дерева, а только на количество содержащихся в нем узлов. Следовательно, случайные величины У; з и У„; независимы. Аналогично, правое поддерево, экспоненциальная высота которого равна У„;, строится случайным образом нз и — г ключей, ранги которых больше г. Структура этого дерева не зависит ат В„, так что случайные величины У„; и Я„; независимы. Следовательно, Часть Ш. Структуры данных 330 2 Е[птах(У; 1,У„;)] < з=1 2 < — ~~1 (Е [У, 1] + Е [У„;]) (в соответствии с (В.21)) (см. упражнение В.3-4). зз-1 Е [У„] < — ~> Е [Уз]. з=о (12.2) Используя метод подстановок, покажем, что для всех натуральных и рекуррентное соотношение (12.2) имеет следующее решение: Е[У„] <— При этом мы воспользуемся тождеством (12.3) (В упражнении 12.4-1 предлагается самостоятельно доказать данное тождество.) Убедимся, что для базовых случаев полученные границы справедливы: О = УО = Е [УО] < — [ [ = -з 4 з,З,з' 4' 1 /1+ 3'1 1 = У1 = Е [У1] < — [ ~ = 1.

4 [, З,з' Используя подстановку, получаем: Е [У„] < — ~ Е [Уз] < з=о 4" з(з.зз) з ~(зз-з) 1 и+3 (в соответствии с гипотезой индукции) (в соответствии с (12.3)) Каждый член Е [УО], Е [У1],..., Е [У„1] в последней сумме встречается дважды: один раз как Е [У; 1], и второй — как Е [У„;], так что мы получаем следующее рекуррентное соотношение: Глава 12. Бинарные деревья поиска 331 1 (и+ 3)! п 4! (и — 1)! 1 (и+ 3)! 4 3!и! 1 и + 3 Итак, мы получили границу для Е ]У„], но наша конечная цель — найти границу Е [Х„].

В упражнении 12.4-4 требуется показать, что функция Г (х) = 2* выпуклая вниз (см. раздел В.З). Таким образом, мы можем применить неравенство Йенсена (В.25), которое гласит, что 2н!х.! < Е Рх.1 Е]У] и получить, что 1(п+3''! 1 (и+3)(п+2)(п+1) пз+бп +11п+6 6 24 Логарифмируя обе части неравенства, находим, что Е 1Х„] = О(!кп). Таким образом, нами доказана следующая теорема. Теорема 12.4. Математическое ожидание высоты случайного бинарного дерева поиска с и ключами равно О (!б и).

Упражнения 12.4-1. Докажите уравнение (12.3). 12.4-2. Приведите пример бинарного дерева поиска с и узлами, такого что средняя глубина узла в дереве равна О (1к и), в то время как высота дерева— ы (1я и). Найдите асимптотическую верхнюю границу высоты бинарного дерева поиска с и узлами, средняя глубина узла в котором составляет О (1я и). 12.4-3. Покажите, что при нашем определении случайных бинарных деревьев поиска с п узлами они не являются равновероятными.

(Указание: рассмотрите все возможные деревья при п = 3.) 12.4-4. Покажите, что функция ) (х) = 2* является выпуклой вниз. * 12.4-5. Рассмотрим алгоритм КАмюм~гнпЯаскзокт, работающий с входной последовательностью из п различных чисел. Докажите, что для любой константы й ) О время работы алгоритма превышает О (п!яп) толью для О (1/п~)-й части всех возможных и! перестановок. 332 Часть 01.

Структуры данных Задачи 12-1. Бинарные деревья поиска с одинаковыми ключами Одинаковые ключи приводят к проблеме при реализации бинарных деревьев поиска. а) Чему равно асимптотическое время работы процедуры Ткал 1мзнкт при вставке п одинаковых ключей в изначально пустое дерево? Мы предлагаем улучшить алгоритм Ткле 1нзнкт, добавив в него перед строкой 5 проверку равенства Ьеу [х] = Ьеу [х], а перед строкой 11— проверку равенства Ьеу [я] = Ьеу [у]. Если равенства выполняются, мы реализуем одну из описанных далее стратегий.

Для каждой из них найдите асимптотическое время работы при вставке п одинаковых ключей в изначально пустое дерево. (Описания приведены для строки 5, в которой сравниваются ключи х и х. Для строки 11 замените в описании х на у.) б) Храним в узле х флаг Ь [х] с логическим значением гл~.зе или тле, которое и определяет выбор (е~( [х] нли г(дй1 [х] при вставке ключа со значением, равным ключу х.

Значение флага при каждой такой вставке изменяется на противоположное, что позволяет чередовать выбор дочернего узла. в) Храним все элементы с одинаковыми ключами в одном узле при помощи списка„и при вставке просто добавляем элемент в этот список. г) Случайным образом выбираем дочерний узел (еГг [х] или ~дМ [х]. (Каково будет время работы такой стратегии в наихудшем случае? Оцените среднее время работы данной стратегии.) 12-2. Цифровые деревья Пусть имеется две строки а = аоа1... ар и Ь = ЬоЬ1...

Ьд, в которых все символы принадлежат некоторому упорядоченному множеству. Мы говорим, что строка а лексикографически меныие строки Ь, если выполняется одно из двух условий. 1) Существует целое 0 < д < ш(п(р, д), такое что а; = Ь; для всех (=0,1,...,д — 1иа <Ь. 2) р < д и для всех г = О, 1,..., р выполняется равенство а; = Ь;. Например, если а и Ь вЂ” битовые строки, то 10100 < 10110 в соответствии с правилом 1 (здесь з = 3), а 10100 < 101000 согласно правилу 2. Такое упорядочение подобно упорядочиванию по алфавиту слов в словаре естественного языка. Глава 12. Бинарные деревья поиска 333 ( р 4КФФ :; |0'7 з г,~ Рнс.

12.5. Цифровое дерево. Ключ узла определяется путем прохода от корня к данному узлу и не должен храниться в дереве. Темным цветом показаны промежуточные узлы, не имеющие ключей Структура цифрового дерева (гайх 1гее) показана на рис. 12.5. Приведенное на рисунке дерево хранит битовые строки 1011, 10, 011, 100 и О. При поиске ключа а = аоа1... ар на г-м шаге мы переходим к левому узлу, если сч = О, и к правому, если а; = 1. Пусть Я вЂ” множество различных бинарных строк с суммарной длиной и. Покажите, как использовать цифровое дерево для лексикографической сортировки за время 9 (и). Для примера, приведенного на рис.

12.5, отсортированная последовательность должна выглядеть следующим образом: О, 011, 10, 100, 1011. 12-3. Средняя глубина вершины в случайном бинарном дереве поиска В данной задаче мы докажем, что средняя глубина узла в случайном бинарном дереве поиска с п узлами равна О (!я и). Хотя этот результат и является более слабым, чем в теореме 12.4, способ доказательства демонстрирует интересные аналогии между построением бинарного дерева поиска и работой алгоритма КАмпоьпхнп Я01скзокт из раздела 7.3.

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

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

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

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