Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 73
Текст из файла (страница 73)
2«) «'Е: 2.)~ 6 «т7 5 26: 5) ~~'.:25 2 «'~',73 ) ««5 ;В 2; а~26 Р~ ,;„Ь ~-Ф 6К: 6«) с,— 6«693 с., ' г«- ««': 25 5 .')'::Й а! ' С.с: 6 «"Й5) Ф «1: 25,3 ®2.".'3 6К.ф Д Глава 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,...,и)) является элемент множества с г-м в порядке возрастания ключом. Мы знаем, что любая порядковая статистика может быть найдена в неупорядоченном множестве за время О (и).
В этом разделе вы увидите, каким образом можно изменить красно-черные деревья для того, чтобы находить порядковую статистику за время О (!кп). Вы также узнаете, каким образом можно находить ранг элемента — его порядковый номер в линейно упорядоченном множестве — за то же время О (1б п).
На рис. 14.1 показана структура данных, которая поддерживает быстрые операции порядковой статистики. Дерево порядковой статистики Т (оп)ег-з!аг1з!1с пес) представляет собой просто красно-черное дерево с дополнительной информацией, хранящейся в каждом узле. Помимо обычных полей узлов красно-черного дерева Иеу [х], со1ог [х], р (х], 1еГг [х] и пдлг [х], в каждом узле дерева порядковой статистики имеется поле а1зе [х], которое содержит количество внутренних) узлов в поддереве с корневым узлом х (включая сам х), т.е. размер поддерева. Если мы определим размер ограничителя как О, т.е.
згяе [ги! [Т]] = О, то получим тождество аьае [х] = з1зе [1е~г [х]] + а!ае [г!961 [х]] + 1. В дереве порядковой статистики условие различности всех ключей не ставится. Например, на рис. 14.1 имеются два ключа со значением 14, и два— с значением 21. В случае наличия одинаковых ключей определение ранга оказывается нечетким, и мы устраняем неоднозначность дерева порядковой статистики, определяя ранг элемента как позицию, в которой будет выведен данный элемент при центрированном обходе дерева.
Например, на рис. 14.1 ключ 14, хранящийся в черном узле, имеет ранг 5, а в красном — ранг 6. От ~ . -.- 12~-.-.. .Э Л: [,Ж Рис. !4.1. Дерево порядковой статистики, являющееся расширением красно-черного дерева Глава 14. Расширение структур данных 367 Выборка элемента с заданным рангом Перед тем как будет изучен вопрос об обновлении информации о размере поддеревьев в процессе вставки и удаления, давайте посмотрим на реализацию двух запросов порядковой статистики, которые используют дополнительную информацию. Начнем с операции поиска элемента с заданным рангом. Процедура 08 8ЕЕЕст(х, 1) возвращает указатель на узел, содержащий 1-й в порядке возрастания ключ в поддереве, корнем которого является х (так что для поиска 1-го в порядке возрастания ключа в дереве порядковой статистики Т мы вызываем процедуру как 08 8~.ест(тоо1 [Т],1): 08 8ЕЕЕСТ(х, 1) 1 т — а1ае[1е11[х]]+1 2 Ы1=т 3 Феп ге1пгп х 4 енен1 < т 5 1ьеп ге1пгп 08 8еьест(1е71[х],1) 6 е1ае ге1пгп 08 8н.ест(пдй[х],1 — т) Идея, лежащая в основе процедуры 08 8е1.ест, аналогична идее, лежащей в основе алгоритмов, рассматривавшихся в главе 9.
Значение атее [1е11 [х]] представляет собой количество узлов, которые при центрированном обходе дерева с корнем в узле х будут выведены до узла х. Таким образом, акае [1е9 [х]] + 1 представляет собой ранг узла х в поддереве, юрием которого является х. В первой строке псевдокода процедуры 08 8ееест мы вычисляем т — ранг узла х в поддереве, для которого он является корнем. Если 1 = т, то узел х является 1-м в порядке возрастания элементом и мы возвращаем его в строке 3. Если же 1 < т, то 1-й в порядке возрастания элемент находится в левом поддереве, так что мы рекурсивно ищем его в строке 5. Если 1 > т, то исюмый элемент находится в правом поддереве и мы делаем соответствующий рекурсивный вызова в строке 6, с учетом того, что 1-й в порядке возрастания в дереве с корнем х элемент является (1 — т)-м в порядке возрастания в правом поддереве х. Для того чтобы увидеть описанную процедуру в действии, рассмотрим поиск 17-го в порядке возрастания элемента в дереве порядювой статистики на рис.
14.1. Мы начинаем поиск с корневого узла, ключ которого равен 26, и 1 = 17. Поскольку размер левого поддерева элемента с ключом 26 равен 12, ранг самого элемента — 13. Теперь мы знаем, что элемент с рангом 17 является 17 — 13 = 4-м в порядке возрастания элементом в правом поддереве элемента с ключом 26.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
