Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 75
Текст из файла (страница 75)
В данном разделе мы рассмотрим шаги, которые необходимо выполнить при таком расширении, а также докажем теорему, которая позволит нам упростить расширение красно-черных деревьев. Расширение структур данных можно разбить на четыре шага. 1. Выбор базовой структуры данных. 2. Определение необходимой дополнительной информации, которую следует хранить в базовой структуре данных и поддерживать ее актуальность. 3. Проверка того, что дополнительная информация может поддерживаться основными модифицирующими операциями над базовой структурой данных.
4. Разработка новых операций. Приведенные правила представляют собой общую схему, которой вы не обязаны жестко следовать. Конструирование — это искусство, зачастую опирающееся на метод проб н ошибок, и все шаги могут на практике выполняться параллельно. Так, нет особого смысла в определении дополнительной информации и разработке новых операций (шаги 2 н 4), если мы не в состоянии эффективно поддерживать работу с этой информацией. Тем не менее, описанная схема позволяет с пониманием дела направлять ваши усилия, а также помочь в организации документирования расширенной структуры данных. Мы следовали приведенной схеме при разработке деревьев порядковой статистики в разделе 14.1. На шаге 1 в качестве базовой структуры данных мы выбрали красно-черные деревья в связи с их эффективной поддержкой других операций порядковых над динамическим множеством, таких как Мпммим, МАх1мОм, ЯиссеззОк и Рке1эесеЯЯОк.
На шаге 2 мы добавили в структуру данных поле з1яе, в котором каждый узел х хранит размер своего поддерева. В общем случае дополнительная информация делает операции более эффективными, что наглядно видно на примере операций ОБ безвест и ОБ Клик, которые при использовании поля а1яе выполняются за время О (1бп). Зачастую дополнительная информация представляет собой не данные, а указатели, как, например, в упражнении 14.2-1. На следующем шаге мы убедились в том, что модифицирующие операции вставки и удаления в состоянии поддерживать поле акае с неизменным асимптотическим временем работы О (1бп). В идеале для поддержки дополнительной информации требуется обновлять только малую часть элементов структуры данных. Например, если хранить в каждом узле его ранг в дереве, то процедуры 08 ЯЕьест и ОВ КАж будут работать быстро, но вставка нового минимального Глава 14.
Расширение структур данных 373 элемента потребует при такой схеме внесения изменений в каждый узел дерева. При хранении размеров поддеревьев вставка нового элемента требует изменения информации только в 0 (1х и) узлах. Последний шаг состоял в разработке операций 08 Злгдсти ОБ КАнк. В конце концов, именно необходимость новых операций в первую очередь приводит нас к расширению структуры данных. Иногда, вместо разработки новых операций мы используем дополнительную информацию для ускорения существующих (см.
упражнение 14.2-1). расширение красно-черных деревьев При использовании в качестве базовой структуры данных красно-черных деревьев мы можем доказать, что определенные виды дополнительной информации могут эффективно обновляться при вставках и удалениях, делая тем самым шаг 3 очень простым.
Доказательство следующей теоремы аналогично рассуждениям из раздела 14.1 о возможности поддержки поля яге деревьями порядковой статистики. Теорема 14.1 (Расширение красно-черных деревьев). Пусть 1 — поле, которое расширяет красно-черное дерево Т из и узлов, и пусть содержимое поля г' узла х может быть вычислено с использованием лишь информации, хранящейся в узлах х, 1еГ1 [х] и г(дйг [х), включая ЯеЯх]] и 1 [гъдЫ[х]]. В таком случае мы можем поддерживать актуальность информации Г" во всех узлах дерева Т в процессе вставки и удаления без влияния на асимптотическое время работы данных процедур 0 (1к и). Доказалзвльсюиво.
Основная идея доказательства заключается в том, что изменение поля Г узла х воздействует на значения поля 1 только у предюв узла х. Таким образом, изменение Г" [х] может потребовать изменения 1 [р[х]), но не более; изменение 1' [р[х)] может привести только к изменению г' [р [р[х)]], и тд. вверх по дереву. При обновлении г [гоо1[Т]] от этого значения не зависят никакие другие, так что процесс обновлений на этом завершается. Поскольку высота красно-черного дерева равна 0 (1к и), изменение поля г" в узле требует времени О (!кп) для обновления всех зависящих от него узлов. Вставка узла х в Т состоит из двух фаз (см. раздел 13.3).
Во время первой фазы узел х вставляется в дерево в качестве дочернего узла неюторого существующего узла р [х]. Значение г' [х] можно вычислить за время О (1), поскольку, в соответствии с условием теоремы, оно зависит только от информации в других полях х и информации в дочерних по отношению к х узлах; однако дочерними узлами х являются ограничители пн [Т).
После вычисления Г" [х] изменения распространяются вверх по дереву. Таким образом, общее время выполнения первой фазы вставки равно 0 (1кп). Во время второй фазы единственным преобразованием, способным вызвать структурные изменения дерева, являются повороты. Часть 111. Структуры данных 374 Поскольку при повороте изменения затрагивают только два узла, общее время, необходимое для обновления полей г", — О (1к и) на один поворот. Поскольку прн вставке выполняется не более двух поворотов, общее время работы процедуры вставки — О (1к и). Так же, как и вставка, удаление выполняется в две стадии (см.
раздел 13.4). Сначала выполняются изменения в дереве, при которых удаляемый узел замещается следующим за ним, а затем из дерева извлекается удаляемая вершина (илн следующая за ней). Обновления значений Г" занимают время О (1к п), поскольку вносимые изменения носят локальный характер. На втором этапе при восстановлении красно-черных свойств выполняется не более трех поворотов, каждый из которых требует для обновления всех полей г" на пути к корню время, не превышающее О (1кп). Таким образом, общее время удаления, как и вставки, составляет О (1я и). Во многих случаях (в частности, в случае поля зтзе в деревьях порядковой статистики) время, необходимое для обновления полей после вращения, составляет О (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[х]].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
