Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 77
Текст из файла (страница 77)
б. Покажите, что математическое ожидание высоты дерамиды равно 9(1бп) н, следовательно, время поиска заданного значения в дерамиде составляет Е(!к п). Рассмотрим процесс вставки нового узла в существующую дерамиду. Первое, что мы делаем, — назначаем новому узлу случайное значение приоритета. Затем мы вызываем процедуру вставки, названную нами ТккАР-1нзпкт, работа которой показана на рис. 13.10.
в. Объясните, как работает процедура ТкпАР-(мзпкт, Поясните принцип ее работы обычным русским языком и приведите ее псевдокод. (Указание: выполните обычную вставку в бинарное дерево поиска, а затем выполните повороты для восстановления свойства неубывающей пирамиды.) а Покажите, что ожидаемое время работы процедуры ТкпАР-1нкект составляет 6(1б и). Процедура ТкпАР-1мзект выполняет поиск с последующей последовательностью поворотов.
Хотя эти две операции имеют одно и то же ожидаемое время работы, на практике стоимость этих операций различна. Поиск считывает информацию из дерамиды, никак ее не изменяя. Повороты, напротив, приводят к изменению указателей на дочерние и родительские узлы в дерамиде. На большинстве компьютеров операция чтения существенно более быстрая, чем операция записи.
Соответственно, желательно, чтобы поворотов при выполнении процедуры ТкпАР-1нзккт было как можно меньше. Мы покажем, что ожидаемое количество выполняемых процедурой поворотов ограничено константой. Для этого необходимо дать несколько определений, проиллюстрированных на рис. 13.11. Тевый хребеяь бинарного дерева поиска Т представляет собой простой путь от корня к узлу с минимальным значением ключа.
Другими словами, левый хребет представляет собой простой путь, состоящий только из левых ребер. Соответственно, правый хребет представляет собой простой путь, состоящий только из правых ребер. Длина хребта — это количество составляющих его узлов. д. Рассмотрите дерамиду Т непосредственно после того, как в нее с помощью процедуры ТкеАР-1нвект вставляется узел х. Пусть С вЂ” длина правого хребта левого поддерева х, а Р— длина левого хребта правого поддерева х.
Докажите, что общее количество поворотов, которые были выполнены в процессе вставки х, равно С + Р. Часть Ш. Структуры даннык Теперь мы вычислим математическое ожидание значений С и Р. Без потери общности будем считать, что ключи представляют собой натуральные числа 1, 2,..., и, поскольку мы сравниваем их только друг с другом. Пусть для узлов х и у (у ф х) дерамиды Т )с = х. кеу и с' = у. кеу. Определим индикаторную случайную величину Хсь = 1 (у находится в правом хребте левого поддерева х) е.
Покажите, что Хьь = 1 тогда и только тогда, югда у.рпопзу ) х.рпоп1у, у. Беу < х. Беу, а для каждого з, такого, что у. Беу < з. Беу < х. кеу, мы имеем у. рпопзу < х. рпопзу. ж. Покажите, что ()с — г — 1)! Рг(Хсь = 1) = (к — г'+ 1)! 1 (/с — 1+ 1)(к — 1) з. Покажите, что и.
Воспользуйтесь симметрией, чтобы показать, что Е[Р] = 1— 1 и — /с+1 сс Сделайте вывод о том, что математичесюе ожидание количества поворотов, выполняемых при вставке узла в дерамиду, меньше 2. Заключительные замечания Идея балансировки деревьев поиска принадлежит советским математикам ЕМ. Адельсону-Вельсюму и Е.М.
Ландису (2), которые в 1962 году предложили класс сбалансированных деревьев поиска, получивших название "АЧ1.-деревья" (описаны в задаче 13.3). Еще один класс деревьев поиска, называемых 2-3-деревьями, был предложен Д.Э. Хопкрофтом (1.Е. Норсгой, не опубликовано) в 1970 году. Баланс зтих деревьев поддерживается с помощью изменения степеней ветвления в узлах. Обобщение 2-3-деревьев, предложенное Байером Глава 13. Красна-черные деревья 371 (Вауег) и Мак-Крейтом (МсСге!8й!) [34] под названием "В-деревья", рассматривается в главе 18. Красно-черные деревья были предложены Байером [33] под названием "симметричные бинарные В-деревья". Гибас (Оц(Ьаз) и Седжвик (Бебйечч)ск) [154] детально изучили их свойства и предложили использовать концепцию красного а черного цветов.
Андерссон (Апбегззоп) [15] предложил вариант красно-черных деревьев, обладающих повышенной простотой кодирования (который был назван Вейссом (Фе(зз) [349] АА-деревьями). Эти деревья подобны красно-черным деревьям с тем отличием, что левый потомок в них не может быть красным. Дерамиды, рассмотренные в задаче 13.4, были предложены Сиделем (8!обе!) я Арагоном (Агайоп) [307]. Они представляют собой реализацию словаря по умолчанию в ЬЕРА [251], тщательно разработанном наборе структур данных и алгоритмов.
Имеется множество других вариантов сбалансированнь1х бинарных деревьев, вюпочая взвешенно-сбалансированные деревья [262], деревья с !е соседями [243], так называемые "деревья — козлы отпущения" (зсарейоаг ггеез) [126] и др. Возможно, наиболее интересны косые" деревья (зр1ау !геев), разработанные Слитором (81еагог) и Таржаном (Тат]ап) [318] и обладающие свойством саморегуляции (хорошее описание косых деревьев можно найти в работе Таржана [328]). Косые деревья поддерживают сбалансированность без использования дополнительных условий балансировки типа цветов.
Вместо этого всякий раз при обращении аад ним выполняются "косые" операции (включающие, в частности, повороты). Амортизированная стоимость (см, главу 17) таких операций в дереве с и узлами составляет 0(18 и). Альтернативой сбалансированным бинарным деревьям поиска являются списки с пропусками (зк(р йз!) [284], которые представляют собой связанные списки, оснащенные рядом дополнительных указателей. Все словарные операции в таких списках с п элементами имеют ожидаемое время выполнения, равное 0(18 п). Глава 14.
Расширение структур данных Зачастую на практике возникают ситуации, когда "классических" структур данных — таких, как дважды связанные списки, хеш-таблицы или бинарные деревья поиска — оказывается недостаточно для решения поставленных задач. Однако только в крайне редких ситуациях приходится изобретать совершенно новые структуры данных; как правило, достаточно расширить существующую структуру путем хранения в ней дополнительной информации, что позволяет запрограммировать необходимую для данного приложения функциональность.
Однако такое расширение структур данных — далеко не всегда простая задача, в первую очередь, из-за необходимости обновления и поддержки дополнительной информации стандартными операциями над структурой данных. В этой главе рассматриваются две структуры данных, которые построены путем расширения красно-черных деревьев. В разделе 14.1 описывается структура, которая обеспечивает операции поиска порядковых статистик в динамическом множестве. С ее помощью мы можем быстро найти 1-е по порядку наименьшее число или ранг данного элемента в упорядоченном множестве.
В разделе 14.2 рассматривается общая схема расширения структур данных и доказывается теорема, которая может упростить процесс расширения красно-черных деревьев. В разделе 14.3 эта теорема используется при разработке структуры данных, поддерживающей динамическое множество промежутков, например промежутков времени, Такая структура позволяет быстро находить в множестве промежуток, перекрывающийся с данным. 14.1. Динамические порядковые статистики В главе 9 было введено понятие порядковой статистики. В частности, г-й порядковой статистикой множества из и элементов (г е (1, 2,..., и)) является элемент множества с 1-м в порядке возрастания ключом.
Мы видели, что любая порядковая статистика может быть найдена в неупорядоченном множестве за время 0(п). В этом разделе вы увидите, каким образом можно изменить красно-черные деревья для того, чтобы находить порядковую статистику за время 0(1йп). Вы также узнаете, каким образом можно находить ранг элемента — его порядковый номер в линейно упорядоченном множестве — за то же время 0(1й и). 373 Глава 7К Расгннренне струмнур данных ® 714" - вде Рис.
14.1. Дерево порядковой статистики, являюшееся расширением красно-черного дерева. Светлые узлы — красные, темные — черные. Помимо обычных атрибупзв, каждый узел х имеет атрибут е.вие, который предстаапяет собой количество узлов, отличных от ограничителя, в поддереве с корнем к.
На рис. 14.1 показана структура данных, которая поддерживает быстрые операции порядковой статистики. Дерево лорядкиаой статистики Т (оп)ег-з1а11зйс 1гее) представляет собой просто красно-черное дерево с дополнительной информацией, хранящейся в каждом узле. Помимо обычных атрибутов узлов красно- черного дерева х.кед, х.со1ог, х.р, х.1е3г и х.гздЫ, у каждого узла дерева порядковой статистики имеется атрибут х.
езде. Этот атрибут содержит количество внутренних узлов в поддереве с корневым узлом х (включая сам х), т.е. размер полдерева. Если мы определим размер ограничителя как О, т.е. Т. пт1. азде = О, то получим тождество х.леде = х 1еут.азде+ х.гздИ.леде+ 1 В дереве порядковой статистики условие различности всех ключей не ставится. Например, на рис. 14.1 имеются два юпоча со значением 14, и два — со значением 21. При наличии одинаювых ключей определение ранга оказывается нечетким, и мы устраняем неоднозначность дерева порядковой статистики, определяя ранг элемента как позицию, в которой будет выведен данный элемент при центрнрованном обходе дерева. Например, на рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
