Алгоритмы - построение и анализ (1021735), страница 72
Текст из файла (страница 72)
Для поддержки поля згае в первой фазе достаточно просто увеличить значение аезе [х] для каждого узла х на пути от корня к листьям. Новый узел получает значение поля згяе, равное 1. Поскольку вдоль пути имеется О (1яп) листьев, дополнительное время, требующееся для поддержания поля лае в первой фазе, составляет О (!я и).
Во второй фазе структурные изменения дерева вызываются только поворотами, которых, как мы знаем, может быть не больше двух. Кроме того, поворот является локальной операцией — после его выполнения становятся некорректными значения згяе только у двух узлов, вокруг связи между которыми выполняется поворот. Возвращаясь к коду Ьпгт КотАте(Т, х) в разделе 13.2, нам надо просто добавить в него следующие строки: 13 з1зе[у] — 41ае[х] 14 аьзе[х] — аззе[1еЯх]] + аже[тзйЫ[х]] + 1 На рис. 14.2 проиллюстрировано обновление полей агае при поворотах.
Изменения в процедуре Винт КотАте симметричны только что рассмотренным. Поскольку при вставке в красно-черное дерево выполняется не более двух поворотов, дополнительное время, требующееся для поддержки актуальности полей 41зе во второй фазе, равно О (1). Таким образом, общее время вставки в дерево порядковой статистики с п узлами составляет О (1к п), т.е.
остается тем же, что и в случае обычного красно-черного дерева. Удаление узла из красно-черного дерева также состоит из двух фаз — первая удаляет узел из дерева поиска, лежащего в основе красно-черного дерева, а вторая восстанавливает красно-черные свойства, выполняя не более трех поворотов н не внося никаких других структурных изменений (см.
раздел 13.4). В первой фазе из дерева извлекается узел у. Для обновления размеров поддеревьев мы просто проходим по пути от узла у до корня дерева, уменьшая величину поля згяе Глава 14. Расширение структур данных 371 каждого узла на нашем пути. Поскольку вдоль пути в красно-черном дереве с и узлами имеется 0 (!к п) листьев, дополнительное время, требующееся для поддержания поля атее в первой фазе, составляет О (1к т1). Во второй фазе выполняется 0 (1) поворотов, которые требуют соответствующего времени для поддержания актуальности размеров поддеревьев.
Итак, как видим, и вставка, и удаление в состоянии поддерживать корректность значений полей язе в дереве, при этом время их работы в дереве порядковой статистики с и узлами составляет 0 (1к и). Упражнения 14.1-1. Покажите, как работает вызов процедуры ОБ Бщ.нст(гсов [Т[, 10) для дерева Т, изображенного на рис. 14.1. 14.1-2.
Покажите, как работает вызов процедуры ОБ КАнк(Т, х) для дерева Т, изображенного на рис. 14.1, если йеу [х[ = 35. 14.1-3. Напишите нерекурсивную версию процедуры ОБ Бн.кст. 14.1-4. Разработайте рекурсивную процедуру ОБ Клу Клнк(Т, 1с), которая получает в качестве входных параметров дерево Т и ключ 1с и возвращает значение ранга ключа й в динамическом множестве, представленном Т. Считаем, что все ключи в Т различны. 14.1-5. Даны элемент дерева порядковой статистики с и узлами х и неотрицательное целое число 1. Каким образом можно найти г-й в порядке возрастания элемент, начиная отсчет от х, за время 0 (1я и)? 14.1-6. Заметим, что процедуры ОБ Бн.лст и ОБ КА~пс используют поле лзе только для вычисления ранга узла в поддереве, корнем которого является данный узел. Предположим, что вместо этого в каждом узле хранится его ранг в таком поддереве.
Покажите, каким образом можно поддерживать актуальность этой информации в процессе вставки и удаления (вспомните, что эти две операции могут выполшпь повороты). 14.1-7. Покажите, как использовать деревья порядковой статистики для подсчета числа инверсий (см. задачу 2-4) в массиве размером и за время 0 (и 1я и). * 14.1-8. Рассмотрим и хорд окружности, каждая из которых определяется своими конечными точками.
Опишите алгоритм определения количества пар пересекающихся хорд за время 0(п1кп). (Например, если все и хорд представляют собой диаметры, пересекающиеся в центре круга, то правильным ответом будет (")). Считаем, что все конечные точки хорд различны. 372 Часть П1. Структуры данных 14.2 Расширение структур данных При разработке алгоритмов процесс расширения базовых структур данных для поддержки дополнительной функциональности встречается достаточно часто.
В следующем разделе он будет использован для построения структур данных, которые поддерживают операции с промежутками. В данном разделе мы рассмотрим шаги, которые необходимо выполнить при таком расширении, а также докажем теорему, которая позволит нам упростить расширение красно-черных деревьев. Расширение структур данных можно разбить на четыре шага. 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я и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
