Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 78
Текст из файла (страница 78)
14.1 ключ 14, хранящийся в черном узле, имеет ранг 5, а в красном — ранг б. Выборка элемента с заданным рангом Перед тем как будет изучен вопрос об обновлении информации о размере поддеревьев в процессе вставки и удаления, давайте посмотрим на реализацию двух запросов порядковой статистики, которые используют дополнительную информацию. Начнем с операции поиска элемента с заданным рангом. Процедура Об-йеыСт(х,з) возвращает указатель на узел, содержащий з-й в порядке возрастания ключ в поддереве, корнем юторого является х (так что для поиска з-го в порядке возрастания ключа в дереве порядковой статистики Т мы вызываем процедуру как ОБ-Бееест1Т. гоо1, з)). Часть Ш.
Стргктгаы данньп 374 ОБ-БЕьЕСТ(х, 1) 1 г = х.1е71.згяе+1 2 И1== г 3 гетцгп х 4 е1зеИ1 ( г 5 гетпгп ОБ-Бн.пст(х. 1еф,1) 6 е1яе гетпгп ОБ-БН.НСт(х. йд1в1, в — г) В строке 1 псевдокода процедуры ОБ-БвьИСт мы вычисляем т — ранг узла х в поддереве, для которого он является корнем. Значение х. 1е71. атее представляет собой количество узлов, которые идут до х в центрированном обходе поддерева с корнем х. Таким образом, х. 1е77. агхе + 1 является рангом х в поддереве с корнем х. Если 1 = г, то узел х является 1-м в порядке возрастания элементом, и мы возвращаем его в строке 3. Если же 1 < г, то 1-й в порядке возрастания элемент находится в левом поддереве, так что мы рекурсивно ищем его в поддереве х.
1е77 в строке 5. Если же 1 > г, то искомый элемент находится в правом поддереве, и мы делаем соответствующий рекурсивный вызов в строке 6 с учетом того, что 1-й в порядке возрастания в дереве с корнем х элемент является (1 — т)-м в порядке возрастания в правом поддереве х с корнем в х. пд1в1. Для того чтобы увидеть описанную процедуру в действии, рассмотрим поиск 17-го в порядке возрастания элемента в дереве порядковой статистики на рис. 14.1. Мы начинаем поиск с корневого узла, ключ которого равен 26, с 1 = 17.
Поскольку размер левого поддерева элемента с ключом 26 равен 12, ранг самогб элемента — 13. Теперь мы знаем, что элемент с рангом 17 является 17 — 13 = 4-м в порядке возрастания элементом в правом поддереве элемента с ключом 26. После соответствующего рекурсивного вызова х становится узлом с ключом 41, а в = 4. Поскольку размер левого поддерева узла с ключом 41 равен 5, ранг этого узла в поддереве равен 6. Теперь мы знаем, что искомый узел находится в левом поддереве узла с ключом 41 и его номер в порядке возрастания — 4. После очередного рекурсивного вызова х становится элементом с ключом 30„а его ранг— 2, и мы рекурсивно ищем элемент с рангом 4 — 2 = 2 в поддереве, корнем которого является узел с ключом 38.
Размер его левого поддерева равен 1, так что ранг самогб узла с ключом 38 равен 2, и это и есть наш искомый элемент, указатель на который и возвращает процедура. Поскольку каждый рекурсивный вызов опускает нас на один уровень в дереве порядковой статистики, общее время работы процедуры ОБ-Бискст в наихудшем случае пропорционально высоте дерева. Поскольку рассматриваемое нами дерево порядковой статистики является красно-черным, его высота равна 0(18 п), где и— количество узлов в дереве. Следовательно, время работы процедуры ОБ-Бн.ест в динамическом множестве из и элементов равно 0(18 и). Определение ранга элемента Процедура ОБ-Клик, псевдокод которой приведен далее, по заданному указателю на узел х дерева порядковой статистики Т возвращает позицию данного узла при центрированном обходе дерева.
315 Гнаеа 14 Расширение структур асаньи ОБ-КАнк(Т, х) 1 т = х.1е11.неве+1 2 у =х 3 зтЬПе у ~ Т. тоо! 4 Иу == у.р.пдЫ 5 т = т+у.р.1е51.н1зе+ 1 6 у=у.р 7 гегпгв т Процедура работает следующим образом. Ранг х можно рассматривать как число узлов, предшествующих х при центрированном обходе дерева, плюс 1 для самогб узла х. Процедура ОЗ-Кянк поддерживает следующий инвариант цикла. В начале каждой итерации цикла «Ьйе в строках 3-6 т представляет собой ранг х.хеу в поддереве, корнем которого является узел у.
Мы воспользуемся этим инвариантом для того, чтобы показать корректность ра- боты процедуры ОЯ-КАнк. Инициализации. Перед первой итерацией строка 1 устанавливает т равным рангу х, Ьеу в поддереве с корнем х. Присвоение у = х в строке 2 делает инвариант истинным при первом выполнении проверки в строке 3. Сохранение. В конце каждой итерации цикла «Ы1е выполняется присвоение у = у.р. Таким образом, необходимо показать, что если т — ранг х. Ьеу в поддереве с корнем у в начале выполнения тела цикла, то в конце т становится рангом х.lсеу в поддереве, корнем которого является у.р. В каждой итерации цикла «ЬПе мы рассматриваем поддерево, корнем которого является у.р. Мы уже подсчитали количество узлов в поддереве с корнем в узле у, который предшествует х при центрированном обходе дерева, так что теперь мы должны добавить узлы из поддерева, корнем которого является "брат" у 1и который также предшествует х при центрированном обходе дерева), и добавить 1 для самогб у.р, если, конечно, этот узел также предшествует х.
Если у — левый дочерний узел, то ни у. р, ни любой узел из правого полдерева у. р не может предшествовать х, так что т остается неизменным. В противном случае у является правым дочерним узлом, и все узлы в поддереве левого потомка у.р предшествуют х, так же как и самому у.р. Соответственно, в строке 5 мы добавляем у.р. 1е5с. нгае + 1 к текущему значению т. Завершение. Цикл завершается, когда у = Т. тоо1, так что поддерево, корнем которого является у, представляет собой все дерево целиком, и, таким образом, т является рангом х.1сеу в дереве в целом.
В качестве примера рассмотрим работу процедуры ОБ-Клик с деревом порядковой статистики, показанным на рис. 14.1. Если мы будем искать ранг узла с ключом 38, то получим следующую последовательность значений у.йеу и т в начале цикла «Ы1е. Часть П1. Структуры данных 17б Итерация у.кеу т 1 38 2 2 30 4 3 41 4 4 2б 17 Процедура возвращает ранг 17. Поскольку каждая итерация цикла зчй11е занимает время 0(1), а у при каждой итерации поднимается на один уровень вверх, общее время работы процедуры ОБ-КА1чк в наихудшем случае пропорционально высоте дерева, те. равно 0(18 и) в случае дерева порядковой статистики с и узлами.
Поддержка размера поддеревьев При наличии атрибута в1ге в каждом узле процедуры ОЯ-Яееест и ОЯ-КА1чк позволяют быстро вычислять порядковые статистики. Однако этот атрибут будет совершенно бесполезным без корректного обновления базовыми модифицирующими операциями над красно-черными деревьями. Давайте рассмотрим, какие изменения нужно внести в алгоритмы вставки и удаления для того, чтобы они поддерживали поля размеров поддеревьев при сохранении асимптотического времени работы каждой операции. В разделе 13,3 мы видели, что вставка в красно-черное дерево состоит из двух фаз.
Первая фаза заключается в проходе вниз по дереву и вставке нового узла в качестве дочернего для уже существующего. Во второй фазе выполняется проход вверх по дереву, при котором выполняются изменения цветов узлов и повороты для сохранения красно-черных свойств дерева. Для поддержки размеров поддеревьев в первой фазе достаточно просто увеличить значение х.вгике для каждого узлах на простом пути от корня к листьям. Новый узел получает значение атрибута вгае, равное 1. Поскольку вдоль пути имеется 0(18 и) узлов, дополнительное время, требующееся для поддержания атрибута ваке в первой фазе, составляет 0(18 и).
Во второй фазе структурные изменения дерева вызываются только поворотами, которых, как мы знаем, может быть не больше двух. Кроме того, поворот является локальной операцией — после его выполнения становятся некорректными значения вазе только у двух узлов, вокруг связи между которыми выполняется поворот. Возвращаясь к коду (.еет-КотАТЕ(Т, х) в разделе 13.2, необходимо просто добавить в него следующие строки. 13 у.вьве = х.вгике 14 х, ввве = х. 1еЯ.
вьве + х. тд1с1. визе + 1 На рис, 14.2 проиллюстрировано обновление атрибутов. Изменения процедуры К1онт-КотАте симметричны только что рассмотренным. Поскольку при вставке в красно-черное дерево выполняется не более двух поворотов, дополнительное время, требующееся для поддержки актуальности атрибутов вате во второй фазе, равно 0(1). Таким образом, общее время встав- Глава /к Раснзаренне структур данных 377 ( егг"Котлте(Т, х) )з .т ';-,Уь К!опт-иотнте(Т, т) Рне. 147К Обновление размеров поддеревьев в процессе поворотов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
