Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 74
Текст из файла (страница 74)
После соответствующего рекурсивного вызова х становится узлом с ключом 41, а 1 = 4. Поскольку размер левого поддерева узла с ключом 41 равен 5, ранг этого узла в поддереве равен 6. Теперь мы знаем, что искомый узел находится в левом поддереве узла с ключом 41, и его номер в порядке возрастания — 4. 368 Часть 18. Структуры данных После очередного рекурсивного вызова х становится элементом с ключом 30, а его ранг — 2, и мы рекурсивно ищем элемент с рангом 4 — 2 = 2 в поддереве, корнем которого является узел с ключом 38.
Размер его левого поддерева равен 1, так что ранг самого узла с ключом 38 равен 2, и это и есть наш искомый элемент, указатель на который и возвращает процедура. Поскольку каждый рекурсивный вызов опускает нас на один уровень в дереве порядковой статистики, общее время работы процедуры ОБ Басист в наихудшем случае пропорционально высоте дерева.
Поскольку рассматриваемое нами дерево порядковой статистики является красно-черным деревом, его высота равна 0(18п), где п — количество узлов в дереве. Следовательно, время работы процедуры ОЯ Бесест в динамическом множестве из и элементов равно О 118 и). Определение ранга элемента Процедура 08 КАмк, псевдокод которой приведен далее, по заданному указателю на узел х дерева порядковой статистики Т возвращает позицию данного узла при центрированном обходе дерева: 08 КАмк(Т, х) ! г — агхе[1ег2[х]] + 1 2 у -х 3 иййе у ~ гоо![Т] 4 ($о н у = пдй1[р[уП 5 гйеп г — г + з!ле[!е~1[р[у]]] + 1 6 у ~ — р[у] 7 ге!пгп г Процедура работает следующим образом.
Ранг х можно рассматривать как число узлов, предшествующих х при центрированном обходе дерева, плюс 1 для самого узла х. Процедура ОБ Клик поддерживает следующий инвариант цикла. В начале каждой итерации цикла иЫ1е в строках 3-6 г представляет собой ранг йеу[х] в поддереве, корнем которого является узел у. Мы воспользуемся этим инвариантом для того, чтобы показать корректность работы процедуры ОЯ КАмк. Инициализация.
Перед первой итерацией строка 1 устанавливает г равным рангу кеу [х] в поддереве с корнем х. Присвоение у — х в строке 2 делает инвариант истинным при первом выполнении проверки в строке 3. Сохранение. В конце каждой итерации цикла и'Ы1е выполняется присвоение у — р [у]. Таким образом, мы должны показать, что если г — ранг йеу [х] в поддереве с корнем у в начале выполнения тела цикла, то в конце г становится рангом йеу [х] в поддереве, корнем которого является р [у].
В каждой Глава 14. Расширение структур данных 369 итерации цикла нЫ!е мы рассматриваем поддерево, корнем которого является р[у]. Мы уже подсчитали количество узлов в поддереве с корнем в узле у, который предшествует х при центрированном обходе дерева, так что теперь мы должны добавить узлы из поддерева, корнем которого является "брат*' у (и который также предшествует х при центрированном обходе дерева), а также добавить 1 для самого р [у] — если, конечно, этот узел также предшествует х. Если у — левый потомок, то ни р [у], ни любой узел из поддерева правого потомка р [у] не могут предшествовать х, так что т остается неизменным. В противном случае у является правым потомком, и все узлы в поддереве левого потомка р [у] предшествуют х, так же как и р [у].
Соответственно, в строке 5 мы добавляем з1зе [1е72 [р [у]]] + 1 к текущему значению т. Завершение. Цикл завершается, когда у = тоо1 [Т], так что поддерево, корнем которого является у, представляет собой все дерево целиком и, таким образом, т является рангом Йеу [х] в дереве в целом. В качестве примера рассмотрим работу процедуры ОЯ КАнк с деревом порядковой статистики, показанным на рис. 14.1. Если мы будем искать ранг узла с ключом 38, то получим следующую последовательность значений йеу [у] и т в начале цикла чтй1!е.
Итерация йеу [у] т 1 38 2 2 30 4 3 41 4 4 26 17 Таким образом, по окончании работы процедура возвращает значение ранга, равное 17. Поскольку каждая итерация цикла занимает время 0(1), а у при каждой итерации поднимается на один уровень вверх, общее время работы процедуры 08 КАнк в наихудшем случае пропорционально высоте дерева, т.е. равно 0 (18 и) в случае дерева порядковой статистики с и узлами. Поддержка размера поддеревьев При наличии поля згяе в узлах дерева процедуры ОБ Бн.нст и ОБ Клик позволяют быстро вычислять порядковые статистики. Однако это поле оказывается совершенно бесполезным, если оно не будет корректно обновляться базовыми модифицирующими операциями над красно-черными деревьями.
Давайте рассмотрим, какие изменения надо внести в алгоритмы вставки и удаления для того, чтобы они поддерживали поля размеров поддеревьев при сохранении асимптотического времени работы. Часть П1. Структуры данных 370 1 19,>3 '"' 99 ', ,,'й ЬЬГГ Ко!ать~'7, и) аклп копна~ ~', у~ Рис. 14.2. Обновление размеров поддеревьев в процессе поворота В разделе 13.3 мы видели, что вставка в красно-черное дерево состоит из двух фаз. Первая фаза заключается в проходе вниз по дереву и вставке нового узла в качестве дочернего для уже существующего. При второй фазе выполняется проход вверх по дереву, при котором выполняются изменения цветов узлов и повороты для сохранения красно-черных свойств дерева.
Для поддержки поля згае в первой фазе достаточно просто увеличить значение аезе [х] для каждого узла х на пути от корня к листьям. Новый узел получает значение поля згяе, равное 1. Поскольку вдоль пути имеется О (1яп) листьев, дополнительное время, требующееся для поддержания поля лае в первой фазе, составляет О (!я и). Во второй фазе структурные изменения дерева вызываются только поворотами, которых, как мы знаем, может быть не больше двух. Кроме того, поворот является локальной операцией — после его выполнения становятся некорректными значения згяе только у двух узлов, вокруг связи между которыми выполняется поворот.
Возвращаясь к коду Ьпгт КотАте(Т, х) в разделе 13.2, нам надо просто добавить в него следующие строки: 13 з1зе[у] — 41ае[х] 14 аьзе[х] — аззе[1еЯх]] + аже[тзйЫ[х]] + 1 На рис. 14.2 проиллюстрировано обновление полей агае при поворотах. Изменения в процедуре Винт КотАте симметричны только что рассмотренным. Поскольку при вставке в красно-черное дерево выполняется не более двух поворотов, дополнительное время, требующееся для поддержки актуальности полей 41зе во второй фазе, равно О (1).
Таким образом, общее время вставки в дерево порядковой статистики с п узлами составляет О (1к п), т.е. остается тем же, что и в случае обычного красно-черного дерева. Удаление узла из красно-черного дерева также состоит из двух фаз — первая удаляет узел из дерева поиска, лежащего в основе красно-черного дерева, а вторая восстанавливает красно-черные свойства, выполняя не более трех поворотов н не внося никаких других структурных изменений (см. раздел 13.4). В первой фазе из дерева извлекается узел у.
Для обновления размеров поддеревьев мы просто проходим по пути от узла у до корня дерева, уменьшая величину поля згяе Глава 14. Расширение структур данных 371 каждого узла на нашем пути. Поскольку вдоль пути в красно-черном дереве с и узлами имеется 0 (!к п) листьев, дополнительное время, требующееся для поддержания поля атее в первой фазе, составляет О (1к т1). Во второй фазе выполняется 0 (1) поворотов, которые требуют соответствующего времени для поддержания актуальности размеров поддеревьев. Итак, как видим, и вставка, и удаление в состоянии поддерживать корректность значений полей язе в дереве, при этом время их работы в дереве порядковой статистики с и узлами составляет 0 (1к и).
Упражнения 14.1-1. Покажите, как работает вызов процедуры ОБ Бщ.нст(гсов [Т[, 10) для дерева Т, изображенного на рис. 14.1. 14.1-2. Покажите, как работает вызов процедуры ОБ КАнк(Т, х) для дерева Т, изображенного на рис. 14.1, если йеу [х[ = 35. 14.1-3. Напишите нерекурсивную версию процедуры ОБ Бн.кст.
14.1-4. Разработайте рекурсивную процедуру ОБ Клу Клнк(Т, 1с), которая получает в качестве входных параметров дерево Т и ключ 1с и возвращает значение ранга ключа й в динамическом множестве, представленном Т. Считаем, что все ключи в Т различны. 14.1-5. Даны элемент дерева порядковой статистики с и узлами х и неотрицательное целое число 1. Каким образом можно найти г-й в порядке возрастания элемент, начиная отсчет от х, за время 0 (1я и)? 14.1-6.
Заметим, что процедуры ОБ Бн.лст и ОБ КА~пс используют поле лзе только для вычисления ранга узла в поддереве, корнем которого является данный узел. Предположим, что вместо этого в каждом узле хранится его ранг в таком поддереве. Покажите, каким образом можно поддерживать актуальность этой информации в процессе вставки и удаления (вспомните, что эти две операции могут выполшпь повороты). 14.1-7. Покажите, как использовать деревья порядковой статистики для подсчета числа инверсий (см.
задачу 2-4) в массиве размером и за время 0 (и 1я и). * 14.1-8. Рассмотрим и хорд окружности, каждая из которых определяется своими конечными точками. Опишите алгоритм определения количества пар пересекающихся хорд за время 0(п1кп). (Например, если все и хорд представляют собой диаметры, пересекающиеся в центре круга, то правильным ответом будет (")). Считаем, что все конечные точки хорд различны. 372 Часть П1. Структуры данных 14.2 Расширение структур данных При разработке алгоритмов процесс расширения базовых структур данных для поддержки дополнительной функциональности встречается достаточно часто. В следующем разделе он будет использован для построения структур данных, которые поддерживают операции с промежутками.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
