Алгоритмы - построение и анализ (1021735), страница 71
Текст из файла (страница 71)
В этом разделе вы увидите, каким образом можно изменить красно-черные деревья для того, чтобы находить порядковую статистику за время О (!кп). Вы также узнаете, каким образом можно находить ранг элемента — его порядковый номер в линейно упорядоченном множестве — за то же время О (1б п). На рис.
14.1 показана структура данных, которая поддерживает быстрые операции порядковой статистики. Дерево порядковой статистики Т (оп)ег-з!аг1зг1с пес) представляет собой просто красно-черное дерево с дополнительной информацией, хранящейся в каждом узле. Помимо обычных полей узлов красно-черного дерева Иеу [х], со1ог [х], р (х], 1еГг [х] и пдлг [х], в каждом узле дерева порядковой статистики имеется поле а1зе [х], которое содержит количество внутренних) узлов в поддереве с корневым узлом х (включая сам х), т.е. размер поддерева.
Если мы определим размер ограничителя как О, т.е. зеве [ги! [Т]] = О, то получим тождество аьае [х] = з1зе [1е~г [х]] + а!ае [г1961 [х]] + 1. В дереве порядковой статистики условие различности всех ключей не ставится. Например, на рис. 14.1 имеются два ключа со значением 14, и два— с значением 21. В случае наличия одинаковых ключей определение ранга оказывается нечетким, и мы устраняем неоднозначность дерева порядковой статистики, определяя ранг элемента как позицию, в которой будет выведен данный элемент при центрированном обходе дерева.
Например, на рис. 14.1 ключ 14, хранящийся в черном узле, имеет ранг 5, а в красном — ранг 6. От ~ . -. -132~-.-.. г30'з-- '' .Э ' 4з ;з: з, зз'з Рис. !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.
После соответствующего рекурсивного вызова х становится узлом с ключом 41, а 1 = 4. Поскольку размер левого поддерева узла с ключом 41 равен 5, ранг этого узла в поддереве равен 6. Теперь мы знаем, что искомый узел находится в левом поддереве узла с ключом 41, и его номер в порядке возрастания — 4. 368 Часть 1Н. Структуры данных После очередного рекурсивного вызова х становится элементом с ключом 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 мы видели, что вставка в красно-черное дерево состоит из двух фаз. Первая фаза заключается в проходе вниз по дереву и вставке нового узла в качестве дочернего для уже существующего. При второй фазе выполняется проход вверх по дереву, при котором выполняются изменения цветов узлов и повороты для сохранения красно-черных свойств дерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
