Алгоритмы - построение и анализ (1021735), страница 70
Текст из файла (страница 70)
Кроме того, полагаем, что 6 [з] = О. Таким образом, для вставки узла з в АЧ1.-дерево Т мы должны осуществить вызов АЧ1. 1нзнкт(гоо1 [Т], г). г) Покажите, что время работы операции АЧЬ 1нзнкт для АЧ1.-дерева с и узлами равно О (1бп), и она выполняет О(1) поворотов. 360 Часть 111. Структуры данных 13-4. Дерамидыз Если мы вставляем в бинарное дерево поиска набор из и элементов, то получающееся в результате дерево может оказаться ужасно несбалансированным, что приводит к большому времени поиска. Однако, как мы видели в разделе 12.4, случайные бинарные деревья поиска обычно оказываются достаточно сбалансированными. Таким образом, стратегия построения сбалансированного дерева для фиксированного множества элементов состоит в случайной их перестановке с последующей вставкой в дерево.
Но что делать, если все элементы недоступны одновременно? Если мы получаем элементы по одному, можем ли мы построить из них случайное бинарное дерево поиска? Рассмотрим структуру данных, которая позволяет положительно ответить на этот вопрос. Дерамида представляет собой бинарное дерево поиска с модифицированным способом упорядочения узлов. Пример дерамиды показан на рис. 13.9. Как обычно, каждый узел х в дереве имеет значение йеу [х]. Кроме того, мы назначим каждому узлу значение приоритета ргзоп1р [х], которое представляет собой случайное число, выбираемое для каждого узла независимо от других. Мы считаем, что все приоритеты и все ключи в дереве различны.
Узлы дерамиды упорядочены таким образом, чтобы ключи подчинялись свойству бинарных деревьев поиска, а приоритеты — свойству неубывающей пирамиды. ° Если н является левым потомком и, то Йеу [о] < Йеу [и]. ° Если зг является правым потомком и, то йер [зз] > йеу [зз]. ° Если о является потомком и, то ргзоп1у [и] > ргзогйд [и]. Именно эта комбинация свойств дерева и пирамиды и дала название "дерамида" (пеар). Помочь разобраться с дерамидами может следующая интерпретация. Предположим, что мы вставляем в дерамиду узлы хы хз,..., х„со связанными с ними ключами.
Тогда получающаяся в результате дерамида представляет собой дерево, которое получилось бы в результате вставки узлов в обычное бинарное дерево поиска в порядке, определяемом (случайно выбранными) приоритетами, те. рг1огз1у [х;] < рпоп~у [х ] означает, что узел х; был вставлен до узла х .. а) Покажите, что для каждого заданного множества узлов хы хз,..., х„ со связанными с ними ключами и приоритетами (все ключи и приоритеты различны) существует единственная дерамида.
В оригинале — ггеарз; слово, образованное из двух — ггее и Ьеар. Аналогично, из "дерева" и "пирамиды" получился русский зквивалент. — Прим. ред. Глава 13. Красно-черные деревья 361 ~6:4 ) «лаз ', Х~,"5 ~~ с.~ с:»'~ Ъо «лайз -~ Рис. 13.9. Дерамила. Каждый узел имеет метку Йеу [х]: ргзогду [х] б) Покажите, что математическое ожидание высоты дерамиды равно 9 (1К и) и, следовательно, время поиска заданного значения в дерамиде составляет О (1я и). Рассмотрим процесс вставки нового узла в существующую дерамиду. Первое, что мы делаем — это назначаем новому узлу случайное значение приоритета. Затем мы вызываем процедуру ТкнАР 1нзнкт, работа которой показана на рис. 13.10.
На рис. 13.10а показана исходная дерамида; на рис. 13.10б — та же дерамида после вставки узла с ключом С и приоритетом 25. Рис. 13.10в-г изображают промежуточные стадии вставки узла с ключом Р и приоритетом 9, а рис. 13.10д — получившуюся в результате дерамиду. На рис. 13.10е показана дерамида после вставки узла с ключом Е и приоритетом 2. в) Объясните, как работает процедура ТкнАР 1нзнкт.
Поясните принцип ее работы обычным русским языком и приведите ее псевдокод. (Указание: выполните обычную вставку в бинарное дерево поиска, а затем выполните повороты для восстановления свойства неубывающей пирамиды.) г) Покажите, что математическое ожидание времени работы процедуры Ткнлг 1нзнкт составляет О (1к и). Процедура ТкнАР 1хзнкт выполняет поиск с последующей последовательностью поворотов. Хотя эти две операции имеют одно и то же математическое ожидание времени работы, на практике стоимость этих операций различна.
Поиск считывает информацию из дерамиды, никак не изменяя ее. Повороты, напротив, приводят к изменению указателей на дочерние и родительские узлы в дерамиде. На большинстве компьютеров операция чтения существенно более быстрая, чем операция записи. Соответственно, желательно, чтобы поворотов при выполнении процедуры ТкнАг 1нзнкт было как можно меньше.
Мы покажем, что ожидаемое количество выполняемых процедурой поворотов ограничено константой. Часть 111. Структуры данных 362 ««Л 9« Рис. 13.10. Работа алгоритма Таеле !Мзеат Для этого нам надо дать несколько определений, проиллюстрированных на рис. 13.1!. Левый хребет бинарного дерева поиска Т представляет собой путь от корня к узлу с минимальным значением ключа. Другими словами, левый хребет представляет собой путь, состоящий только из левых ребер. Соответственно, правый хребет представляет собой путь, состоящий только из правых ребер.
Длина хребта — это количество составляющих его узлов. д) Рассмотрите дерамиду Т после того, как в нее при помощи процедуры ТкеАГ !29зент вставляется узел х. Пусть С вЂ” длина правого ''2Р. 9 ' .' 23:7 2 6К65 5 ,9 — «, А~!О) (Е ф 6А;65,« н Ф:4) гг9' '6«1~ «б5 фЯ~ (63 65 «6::25 3 «1732 Г,,6' ! и: ~05 «л:9. Екав « 7 «, «б.2«) ~Е:2.«5 6 «т7 3 2659 ~~'.:25 2 «'~',73 ) ««3 ;262; а~26Р« ,;„Ь ~-Ф 6К: 65'2 с,— 66693 с., ' г«- ««': 25 3 .')'::Й в! ' С.с: 9 «"Й5) С6,3) Глава 13. Красно-черные деревья 363 Ь ) ~ л й Рнс. 13.11. Хребты в бинарных деревьях поиска (а — левый хребет, б — правый) хребта левого поддерева х, а Р— длина левого хребта правого поддерева х. Докажите, что общее количество поворотов, которые были выполнены в процессе вставки х, равно С+ Р. Теперь мы вычислим математическое ожидание значений С и Р.
Без потери общности будем считать, что ключи представляют собой натуральные числа 1, 2, ..., и, поскольку мы сравниваем их толью друг с другом. Пусть для узлов х и у (х ф у) !с = йеу [х] и 1 = !сеу [у]. Определим индикаторную случайную величину Х; ь = 1 (у находится в правом хребте левого поддерева х) . е) Покажите, что Х, ь = 1 тогда и только тогда, когда ртгот1гу[у] > > ртютзсу [х], !сеу [у] < Иеу [х] и для каждого а такого, что Йеу [у] < < Йеу [а] < Йеу [х], имеем ртзот!1у [у] < ртъотз1у [а]. ж) Покажите, что (!с — 1 — 1)! 1 Рг1Х;а = 1)— (/с — 1+ 1)! (!с — 1+ 1) (й — 1) ' з) Покажите„что ь-1 Е [С] = ~~~,, = 1 — —. з Ц+ 1) !с и) Используя симметрию, покажите, что Е[Р]=1— 1 и — !с+ 1 Часть 111.
Структуры данных к) Сделайте вывод о том, что математическое ожидание количества поворотов, выполняемых при вставке узла в дерамиду, меньше 2. Заключительные замечания Идея балансировки деревьев поиска принадлежит советским математикам ГМ. Адельсону-Вельскому и Е.М. Ландису [2), предложившим в 1962 году класс сбалансированных деревьев поиска, получивших название Ат'!.-деревьев (описанных в задаче 13-3). Еще один класс деревьев поиска, называемых 2-3-деревьями, был предложен Хопкрофтом (ЕЕ. Норсгой, не опубликовано) в 1970 году. Баланс этих деревьев поддерживается при помощи изменения степеней ветвления в узлах.
Обобщение 2-3-деревьев, предложенное Байером (Вауег) и Мак-Крейтом (МсСге18Ь!) [32) под названием В-деревьев, рассматривается в главе 18. Красно-черные деревья предложены Байером (31) под названием "симметричные бинарные В-деревья*'. Гибас (ОшЬаз) и Седжвик (Яебйеичск) [135) детально изучили их свойства и предложили использовать концепцию цветов. Андерсон (Апдегзоп) (15) предложил вариант красно-черных деревьев, обладающих повышенной простотой кодирования (который был назван Вейссом (9Уе(зз) (311) АА- деревьями). Этн деревья подобны красно-черным деревьям с тем отличием, что левый потомок в них не может быть красным. Дерамиды были предложены Сиделем (81ес1е1) и Арагоном (Агайоп) [27!). Они представляют собой реализацию словаря по умолчанию в ЕЕРА, тщательно разработанном наборе структур данных и алгоритмов.
Имеется множество других вариантов сбалансированных бинарных деревьев, включая взвешенно-сбалансированные деревья [230), деревья с !г соседями [213], т.н. "деревья-козлы отпущения" (зсарейоа1 !геев) (108) и другие. Возможно, наиболее интересны "косые'* деревья (зр!ау !геев), разработанные Слитором (81еагог) и Таржаном (Тат)ап) (282), обладающие свойством саморегуляции (хорошее описание косых деревьев можно найти в работе Таржана [292)). Косые деревья поддерживают сбалансированность без использования дополнительных условий балансировки типа цветов.
Вместо этого всякий раз при обращении над ним выполняются косые*' операции (включающие, в частности, повороты). Амортизированная стоимость (см. главу ! 7) таких операций в дереве с и узлами составляет О (1к и). Альтернативой сбалансированным бинарным деревьям поиска являются списки с пропусками (зрйр 11з1) (251), которые представляют собой связанные списки, оснащенные рядом дополнительных указателей.
Все словарные операции в таких списках с и элементами имеют математическое ожидание времени выполнения, равное О (18 и). ГЛАВА 14 Расширение структур данных Зачастую на практике возникают ситуации, когда "классических" структур данных — таких как дважды связанные списки, хеш-таблицы или бинарные деревья поиска — оказывается недостаточно для решения поставленных задач. Однако только в крайне редких ситуациях приходится изобретать совершенно новые структуры данных; как правило, достаточно расширить существующую структуру путем сохранения в ней дополнительной информации„что позволяет запрограммировать необходимую для данного приложения функциональность.
Однако такое расширение структур данных — далеко не всегда простая задача, в первую очередь, из-за необходимости обновления и поддержки дополнительной информации стандартными операциями над структурой данных. В этой главе рассматриваются две структуры данных, которые построены путем расширения красно-черных деревьев. В разделе 14.1 описывается структура, которая обеспечивает операции поиска порядковых статистик в динамическом множестве. С ее помощью мы можем быстро найти 1-е по порядку наименьшее число или ранг данного элемента в упорядоченном множестве.
В разделе 14.2 рассматривается общая схема расширения структур данных и доказывается теорема, которая может упростить расширение красно-черных деревьев. В разделе 14.3 эта теорема используется при разработке структуры данных, поддерживающей динамическое множество промежутков, например, промежутков времени. Такая структура позволяет быстро находить в множестве промежуток, перекрывающийся с данным. Часть 111. Структуры данных Збб 14.1 Динамические порядковые статистики В главе 9 было введено понятие порядковой статистики. В частности, г-й порядковой статистикой множества из п элементов (г Е !1,2,...,и)) является элемент множества с г-м в порядке возрастания ключом. Мы знаем, что любая порядковая статистика может быть найдена в неупорядоченном множестве за время О (и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
