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