Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 80
Текст из файла (страница 80)
142 3 * Пусть З представляет собой ассоциативный бинарный оператор, а а — атрибут, поддерживаемый в каждом узле красно-черного дерева. Предположим, что мы хотим включить в каждый узел х дополнительный атрибут С', такой, что х. С = х д. а З хз. а З... З хт. а, где х д, хз,..., х — центрированный список узлов поддерева, корнем которого является х. Покажите, как обновлять атрибуты ~ после поворотов за время 0(1). Примените свои рассуждения, слегка их модифицирован, к атрибутам зСзе в дереве порядковой статистики. 14.2 4 * Мы хотим добавить к красно-черным деревьям операцию дсВ-Еыддмпкддтп(х, а, Ь), которая выводит все ключи а < к < Ь в красно-черном дереве, корнем кодорого является х. Опишите, как можно реализовать процедуру КВ-Едчддьдпклтп, чтобы время ее работы составляло 6(т + !к и), где т — число выводимых ключей, а и — количество внутренних узлов в дереве.
(Указаниед нет необходимости добавлять новые атрибуты в красно-черное дерево.) 14.3. Деревья отрезков В этом разделе мы расширим красно-черные деревья для поддержки операций над динамическими множествами отрезков. Отрезком называется упорядоченная пара действительных чисел [Сд, Сз[, таких, что Сд < Сз. Отрезок [Сд, Сз] представляет множество (С Е К; Сд < С < Сз). Интервал (Сд, Сз) представляет собой отрезок без конечных точек, т.е. множество (С Е К: Сд < С < Сз), а полуинтерволм [Сд, Сз) н (Сд, Сз[ образуются из отрезка при удалении из него одной из конечных точек.
В случае, когда принадлежность концов несущественна, обычно говорят о промежутках. В данном разделе мы будем работать с отрезками, но расширение результатов на интервалы и полуинтервалы не должно составить для читателя никакого труда. Отрезки удобны для представления событий, которые занимают некоторый промежуток времени. Мы можем, например, сделать запрос к базе данных о том, какие события происходили в некоторый промежуток времени. Рассматриваемая а данном разделе структура данных обеспечивает эффективное средство для поддержки такой базы данных, работающей с промежутками. Часть Ш.
Структуры данных зд2 (а) (ь) (б) Рис. 14.З. Трихотомия отрезков ( и з', (а) Если ( и д перекрываются, возможны четыре ситуации: в кая(лой из них к (ою < з'. ЬздЬ и з'. (от < т. Ьтдь. (4) Отрезки не перекрываются и (. Ьидь < з'. (от. (в) Отрезки не перекрываются и ~'. Ь(дЬ < (. (от. Мы можем представить отрезок 11), (з~ в виде объекта з с атрибутами (. 1ою = 11 (левый, или нижний, конец отрезка) и г. Ь(дЬ = (з (нровый, или верхний, конец).
Мы говорим, что отрезки т и т' нерекрывоютси (очег1ар), если з г) з' ф 6, т.е. если зй 1он) < з'. Ь(дЬ и з'. 1ою < з. ЬздЬ. Для любых двух отрезков т и т' выполняется только одно из трех свойств (трихотомия отрезков) (рис. 14.3): а. з и з' перекрываются; б. т находится слева от т' (т.е. з. Ь(дЬ < з'. 1ов); в. т находится справа от з' (т.е.
з'. ЬздЬ < т. 1ов). Дерево отрезков представляет собой красно-черное дерево, каждый элемент х ж)торого содержит отрезок х. )п(. Деревья отрезков поддерживают следующие операции. 1)чтекчи.-1)чзеит(Т, х) добавляет элемент х, атрибут ш( которого рассматривается как содержащий отрезок, в дерево отрезков Т. 1)чтекчи:1)еьете(т, х) удаляет элемент х из дерева отрезков т. 1)(теичь~.-Беьксн(Т, з) возвращает указатель на элемент х в дереве отрезков Т, такой, что х.гп( перекрывается с отрезком з', или указатель на ограничитель Т, пй, если такого элемента во множестве нет. На рис.
14.4 показано, как дерево отрезков представляет множество отрезков. Давайте рассмотрим этапы расширения структур данных из раздела 14.2 при решении задачи разработки дерева отрезков и реализации операций над ним. Шаг 1. Базовая структура данных В качестве базовой структуры данных мы выбираем красно-черное дерево, каждый узел х которого содержит отрезок х. ш1, а ключом узла является левый конец отрезка х.
ш(. 1ош Таким образом, центрированный обход дерева приводит к перечислению отрезков в порядке сортировки по их левым концам. звз Глана 14 Расыкреике струмиур данньи 2бн26 25а — ЗО 19а-а20 и Гд 16~ — — ~21 (а) 8н9 6~ — — «ГО 5» — -~8 о з 25 ЗО 1О 15 20 0 5 -.- (ц~":,, - (ит (б) Рис. 14А. Дерево отрезков. (в) Мнвкество нз десяти отрезюв, отсортировянных снизу вверх по левой конечной точке. (6) Дерево отрезков. предстквлязощее зто множество. Каждый узел к ащержвт отрезок, показанный няд пунктирной чертой, и максимальное значение конечной точки для всех отрезков поддереве с юрием л, поквзкиное под пунктирной линией. Центрироввнный абищ дерева перечисляет все узлы в отсортироввниом до левым концем порядке. Шаг 2. Дополнительная информация В дополнение к самим отрезкам каждый узел х содержит значение х. тпах, которое представляет собой максимальное значение всех юнечныд точек отрезюв, хранящихся в поддереве, корнем которого является х.
Шаг 3. Поддержка информании Необходимо убедиться в том, что вставка и удаление в дереве с и узлами могут быть выполнены за время О()й и). Определить значение атрибута тах в узле х можно очень просто с использованием атрибутов тах дочерних узлов: х. гпах = п)ах(х.
зп1. ()зд)), х. 1е)а. тах, х. тздЫ. гдах) . Таким образом, по теореме 14.1 вставка в дерево отрезков н удаление из него макет быть выполнена за время О()йп). В действительности, как показано в упр. 14.2.3 и 14.3.1, обновление атрибута тах после вращения может быть выполнено за время О(1). Часть Ш Структуры даккык За4 Шаг 4. Разработка новых операций Единственная новая операция, которую мы хотим разработать, — это 1нтекчА6-8еАхсн[Т, 1), которая осуществляет поиск в дереве Т отрезка, который перекрывается с данным. Если такого отрезка в дереве нет, процедура возвращает указатель на ограничитель Т.
п11. 1нтекчАе-БеАксн [Т, 1) 1 х = Т.гоо1 2 жанне х ф Т. п11 и 1 не перекрывается с х. т1 3 11 х. 1е11 ~ Т. пй и х. 1еЯ. тах > 1. 1ою 4 х = х.1е~1 5 еЬе х = х.яда 6 гетпгп х Для поиска отрезка, который перекрывается с г, мы начинаем с присвоения указателю х корня дерева и выполняем спуск по дереву. Спуск завершается, когда мы находим перекрывающийся отрезок или когда х указывает на ограничитель Т. п11. Поскольку каждая итерация основного цикла выполняется за время 0[1), а высота красно-черного дерева с п узлами равна 0(18п), время работы процедуры 1нтеячхе-8елксн равно 0(18 п).
Прежде чем убедиться в корректности процедуры 1нтекчАе-8еАЕСН, давайте посмотрим, как она работает, на примере дерева, показанного на рис. 14.4. Предположим, что мы хотим найти отрезок, перекрывающийся с отрезком 1 = [22, 25]. Мы начинаем работу с корня, в котором содержится отрезок (16,2Ц, который не перекрывается с отрезком г'. Поскольку значение х. 1еД. тах = 23 превышает Е 1ою = 22, цикл продолжает выполнение с х, указывающим на левый дочерний узел корня.
Этот узел содержит отрезок [8,9], который также не перекрывается с отрезком г. Теперь х. 1еД. тах = 10 меньше 1. 1ою = 22, так что мы переходим к правому дочернему узлу. В нем содержится отрезок (15, 23], перекрывающийся с х, так что процедура возвращает указатель на данный узел. В качестве примера неудачного поиска попробуем найти в том же дереве отрезок, перекрывающийся с отрезком 1 = (11, 14]. Мы вновь начинаем с корня. Поскольку отрезок в корне [16, 2Ц не перекрывается с 1 и поскольку х. 1еД. тах = 23 больше, чем 1. 1ою = 11, мы переходим к левому дочернему узлу корня с отрезком [8, 9].
Отрезок (8, 9] также не перекрывается с г, а х. 1еД, тах = 10, что меньше, чем г. 1ою = 11, поэтому мы переходим вправо (обратите внимание, что теперь в левом поддереве нет ни одного отрезка, перекрывающегося с 1). Отрезок [15, 23] не перекрывается с г, его левый дочерний узел — Т. п11, так что цикл завершается и процедура возвращает указатель на ограничитель Т, пй, Для того чтобы убедиться в корректности процедуры 1нтекчА5-8еАксн, нужно разобраться, почему для поиска достаточно пройти по дереву всего лишь по одному пути от корня.
Основная идея заключается в том, что в любом узле х, если х. 1п1 не перекрывается с 1, дальнейший поиск всегда идет в безопасном направлении, т.е. перекрывающийся отрезок, если таковой имеется в дереве, гарантированно будет обнаружен в исследуемой части дерева. Более точно это свойство сформулировано в следующей теореме. Паза ! б Расгииренис смрукмур данных 385 Теорема 14.2 Любой вызов процедуры!)(тйкчм:Бйдксн(Т, з) возврашает либо узел, отрезок которого перекрывается с отрезком г', либо, если в дереве Т не содержится отрез)ах перекрывающегося с з, Т.
пН. Доказавгелвсигоо. Цикл зтййе в строках 2-5 завершается, если х = Т. пд либо если з перекрывается с х. тй В последнем случае процедура тривиально возвращает корректное значение х. Поэтому нас интересует первый случай, когда цикл завершается из-за того, что х = Т. пИ. Воспользуемся следующим инвариантом цикла зт)гйе в строках 2-5. Если дерево Т содержит отрезок, который перекрывается с з, то этот отреюк находится в поддереве, корнем которого является узел х. Исследуем этот инвариант цикла как обычно. Иняциализация.
Перед выполнением первой итерации в строке 1 переменной х присваивается указатель на корень дерева Т, так что инвариант выполняется. Сохранение. При каждой итерации цикла зт)гйе выполняется либо строка 4, либо строка 5. Покажем, что инвариант цикла сохраняется в любом случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
