Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 79
Текст из файла (страница 79)
Связь, вокруг которой осуществляется поворот, соединяет два узла, атрнбугы лые которых следует обновить. Обновленна локальны, требуют информации нз атрибутов лые узлов к, р н корней поддеревьев, показанных в виде треугольннюв. ки в дерево порядковой статистики с п узлами составляет О(1б и), т.е. остается асимптотически тем же, что и в случае обычного красно-черного дерева. Удаление узла из красно-черного дерева также представляет собой двухфазный процесс — первая фаза удаляет узел из дерева поиска, лежащего в основе красно-черного дерева, а вторал восстанавливает красно-черные свойства, выполняя не более трех поворотов и не внося никаких других структурных изменений (см.
раздел 13.4). В первой фазе из дерева извлекается узел р или выполняется его перемещение вверх по дереву. Для обновления размеров поддеревьев мы просто проходим по простому пути от узла у (начиная с его исходного положения в дереве) до корня дерева, уменьшая величину атрибута ляле каждого узла на нашем пути. Поскольку длина этого пути в красно-черном дереве с и узлами равна 0()ли), дополнительное время, затрачиваемое на поддержку атрибута зеле в первой фазе, составляет О(!я и).
Во второй фазе обрабатываются О(1) поворотов— тем же способом, что и в случае вставки. Итак, и вставка, и удаление в состоянии поддерживать корректность значений атрибутов лазе в дереве, при этом время их работы в дереве порядковой статистики с и узлами составляет О(!б п). Упражнения 141.1 Покажите, как работает вызов процедуры Об-ййЬбст(Т.гоо(, 10) для красно-черного дерева Т, изображенного на рис. 14.1. 141.3 Покажите, как работает вызов процедуры ОБ-Кд)як(Т, х) для дерева Т, изображенного на рис.
14.1, если х. кеу = 35. 141З Разработайте нерекурсивную версию процедуры Ой-йа.бст. 141.4 Разработайте рекурсивную процедуру ОБ-Кит-зхдык(Т,Й), которая получает в качестве входных параметров дерево порядковой статистики Т и ключ )с и возвращает значение ранга ключа 1с в динамическом множестве, представленном Т. Считаем, что все ключи в Т различны.
Часть Ш. Структуры даикык 37а 14.1. 5 Даны элемент з дерева порядковой статистики с и узлами и неотрицательное целое число 1. Каким образом можно найти г-й в порядке возрастания элемент, начиная отсчет от х„за время 0(1й и)? 14.1.6 Заметим, что процедуры ОБ-Веьпст и ОЯ-КАМК используют атрибут агяе только для вычисления ранга узла. Предположим, что вместо этого в каждом узле хранится его ранг в поддереве, корнем которого он является, Покажите, каким образом можно поддерживать актуальность этой информации в процессе вставки и удаления (вспомните, что эти две операции могут выполнять повороты).
14.1. 7 Покажите, как использовать дерево порядковой статистики для подсчета числа инверсий (см. задачу 2.4) в массиве размером п за время О(п 1л и). 14.1.8 * Рассмотрим п хорд окружности, каждая из которых определяется своими конечными точками. Опишите алгоритм определения количества пар пересекающихся хорд за время 0(п 1к п). (Например, если все и хорд представляют собой диаметры, пересекающиеся в центре круга, то правильным ответом будет (")).
Считаем, что все конечные точки хорд различны. 14.2. Расширение структур данных При разработке алгоритмов процесс расширения базовых структур данных для поддержки дополнительной функциональности встречается достаточно часто. В следующем разделе он будет использован для построения структур данных, которые поддерживают операции с промежутками. В данном разделе мы рассмотрим шаги, которые необходимо выполнить в процессе такого расширения, а также докажем теорему, которая во многих случаях позволяет упростить расширение красно-черных деревьев.
Расширение структур данных можно разбить на четыре шага. 1. Выбор базовой структуры данных. 2. Определение необходимой дополнительной информации, которую следует хранить в базовой структуре данных и актуальность которой следует поддерживать. 3. Проверка того, что дополнительная информация может поддерживаться ос- новными модифицирующими операциями над базовой структурой данных. 4. Разработка новых операций.
Приведенные правила представляют собой общую схему, которой вы не обязаны жестко следовать. Проектирование — это искусство, зачастую опирающееся на Глони 1К Расширение смруннвр данных 319 метод проб и ошибок, и все шаги могут на практике выполняться параллельно. Так, иет особого смысла в определении дополнительной информации и разработке новых операций (шаги 2 и 4), если мы не в состоянии эффективно поддерживать эту дополнительную информацию.
Тем не менее описанная схема позволяет с пониманием дела направлять свои усилия, а также помочь в организации документирования расширенной структуры данных. Мы следовали описанной схеме при разработке деревьев порядковой статистики в разделе 14.1. На шаге 1 в качестве базовой структуры данных мы выбрали красно-черные деревья в связи с их эффективной поддержкой других порядковых операций над динамическим множеством, таких как Мпч~мпм, Млхзмпм, ЗйССЕББОК и РКЕОЕСЕББОК. На шаге 2 мы добавили в структуру данных атрибут оьте, в котором каждый узел х хранит размер своего полдерева.
В общем случае дополнительная информация делает операции более эффективными, что наглядно видно на примере операций ОБ-БЕЕЕСт и ОБ-КЛЫК, которые можно было бы реализовать и с использованием одних лишь хранящихся в узлах ключей, но тогда оии не могли бы выполняться за время О(1кп). Зачастую дополнительная информация представляет собой не данные, а указатели, как, например, в упр. 14.2.1. На шаге 3 мы убедились в том, что модифицирующие операции вставки и удаления в состоянии поддерживать атрибут огее с неизменным асимптотическим временем работы 0(1к п).
В идеале для поддержки дополнительной информации требуется обновлять только малую часть элементов структуры данных. Например, если хранить в каждом узле его ранг в дереве, то процедуры ОЯ-БЕСЕСт я ОБ-Клык будут работать быстро, но вставка нового минимального элемента потребует при такой схеме внесения изменений в каждый узел дерева. При хранении размеров поддеревьев вставка нового элемента требует изменения информации только в 0(1й и) узлах. Шаг 4 состоял в разработке операций ОВ-Бесест и ОБ-Клык.
В конце концов, именно необходимость новых операций, в первую очередь, приводит нас к расширению структуры данных. Иногда вместо разработки новых операций ны используем дополнительную информацию для ускорения существующих, как в упр. 14.2.1. Расширение красно-черных деревьев При использовании в качестве базовой структуры данных красно-черных деревьев можно доказать, что определенные виды дополнительной информации могут эффективно обновляться при вставках и удалениях, делая тем самым шаг 3 очень простым. Доказательство следующей теоремы аналогично рассуждениям лз раздела 14.1 о возможности поддержки атрибута огге деревьями порядковой статистики.
Теорема 14.1 (Расшнренне красно-черных деревьев) Пусть Т представляет собой атрибут, который расширяет красно-черное дерево Т из п узлов, и пусть значение 1 каждого узла х зависит только от информации, хранящейся в узлах х, х. 1еП и я, пдЫ, возможно, включая л. 1е11.1 и х. пдп1.1. Зао Часть Ш. Структуры аакаык В таком случае мы можем поддерживать актуальность информации 1 во всех узлах дерева Т в процессе вставки и удаления без влияния на асимптотическое время работы данных процедур 0(1к и). Доказательство. Основная идея доказательства заключается в том, что изменение атрибута 1 узла х воздействует на значения атрибута 1 только у предков узла х. Иначе говоря, изменение т. Г может потребовать обновления х.р.1, но не более того; обновление х.р.1 может привести только к необходимости обновления х.р.р.1, и так далее вверх по дереву.
При обновлении Т. гооь'.1 от этого значения не зависят никакие другие, так что процесс обновлений на этом завершается. Поскольку высота красно-черного дерева равна О(1яп), изменение атрибута 1' в некотором узле требует времени О(1яп) для обновления всех зависящих от него узлов. Вставка узла х в дерево Т состоит из двух фаз (см. раздел 13.3). Во время первой фазы узел х вставляется в дерево в качестве дочернего узла некоторого существующего узла х.р. Значение к.1' можно вычислить за время 0(1), поскольку в соответствии с условием теоремы оно зависит только от информации в других атрибутах з и информации в дочерних по отношению к х узлах; однако дочерними узлами х являются ограничители Т. ль1, После вычисления х.1 изменения распространяются вверх по дереву.
Таким образом, общее время выполнения первой фазы вставки равно 0(1к и). Во время второй фазы единственным преобразованием, способным вызвать структурные изменения дерева, являются повороты. Поскольку при повороте изменения затрагивают только два узла, общее время, необходимое для обновления атрибутов 1, — О(1к и) на один поворот.
Поскольку при вставке выполняется не более двух поворотов, общее время работы процедуры вставки равно 0(1й п). Так же, как и вставка, удаление выполняется в две стадии (см. раздел 13.4). Сначала выполняются изменения в дереве, при которых удаляемый узел извлекается из дерева. Если удаляемый узел имел в этот момент два дочерних узла, то следующий за ним в дереве узел перемещается в позицию удаленного узла. Распространение обновлений 1' имеют стоимость не более О(1к и) в силу локального характера вносимых изменений. На втором этапе при восстановлении красно-черных свойств выполняется не более трех поворотов, каждый из которых требует для распространения обновлений 1 времени, не превышающего 0(!яп). Таким образом, общее время удаления составляет О(1я и).
Во многих случаях (в частности, в случае атрибутов атее в деревьях порядковой статистики) время, необходимое для обновления атрибутов после вращения. составляет 0(1), а не О(1я и), полученное в доказательстве теоремы 14.1. Пример такого поведения можно найти в упр. 14.2.3. Упражнения 14.3.1 Покажите, каким образом расширить дерево порядковой статистики, чтобы операции Млх~мим, Мзьпмим, Яисскззок и Рккпкскззок выполнялись за время даава!К Расидиреиие сидддуиидур ддаииьи 0(1) в наихудшем случае.
Асимптотическая производительность остальных операций над деревом порядковой статистики должна при этом остаться неизменной. Может ли черная высота узлов в красно-черном дереве поддерживаться как атрибут узла дерева без изменения асимптотической производительности операций над красно-черными деревьями? Покажите, как этого достичь (или докажите, что зто невозможно).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
