Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Структура данных
Допустимые операции
Сливаемая пирамида
ВСТАВИТЬ, УДАЛИТЬ, НАЙТИ, ОБЪЕДИНИТЬ, (MIN)
Каждую из вышеуказанных операций можно выполнить за время 0(logN), где N — размер множества, запасенного в этой структуре данных путем использования, как обычно, дерева, сбалансированного по высоте. Если элементы рассматриваемого множества представлены целыми числами от 1 до N, то более сложная реализация этой структуры данных позволяет выполнить N операций над множеством размером N за время 0(N-A(N)), где A(N)—чрезвычайно медленно растущая функция, связанная с обратной функцией Аккермана (например, для ЛГ<22'6, или ~Ю20000, Л(ЛГ)<5).
Стандартные структуры данных, рассмотренные выше, широко используются в алгоритмах вычислительной геометрии. Однако природа геометрических задач привела к созданию специальных, необычных структур данных, две из которых оказались настолько общезначимыми, что целесообразно представить их в данной вводной главе. Эти структуры — дерево отрезков и реберный список с двойными связями.
1.2.3.1. Дерево отрезков
Дерево отрезков, впервые введенное Дж. Бентли [Bentley (1977)], это структура данных, созданная для работы с такими интервалами на числовой оси, концы которых принадлежат фиксированному множеству из N абсцисс. Поскольку множество абсцисс фиксировано, то дерево отрезков представляет собой статическую структуру по отношению к этим абсциссам, т. е. структуру, на которой не разрешены вставки и удаления абсцисс; кроме того, эти абсциссы можно нормализовать, заменяя каждую из них ее порядковым номером при обходе их слева направо. Не теряя общности, можно считать эти абсциссы целыми числами в интервале [1,ЛГ|.
1.2. Алгоритмические основы
25
Дерево отрезков — это двоичное дерево с корнем. Для заданных целых чисел / и г таких, что / < г, дерево отрезков Т(1, г) строится рекурсивно следующим образом: оно состоит из корня v с параметрами B[v] — I и E[v] =г (В и Е мнемонически соответствуют словам «beginning» (начало) и «end» (конец)), а если г—1>\, то оно состоит из левого поддерева T(l, L(B[v]+E[v])/2}) и правого поддерева T(l(B[v] + + ?[f])/2J, г). (Корни этих поддеревьев естественно обозначить черезЛСЫН[и] и ПСЫН[о] соответственно.) Параметры В [v]
Рис. 1.1. Дерево отрезков 7"(4, 15).
и E[v] обозначают интервал [B[v], E[v]] s [/, г], связанный с узлом v. Пример дерева отрезков приведен на рис. 1.1. Интервалы, принадлежащие множеству {[В[и], ?[у]]: и— узел Т(1,г)}, называются стандартными интервалами дерева Т(1,г). Стандартные интервалы, принадлежащие листьям Т(1, г), называются элементарными интервалами1). Можно непосредственно убедиться, что Т(1,г) сбалансировано (все его листья принадлежат двум смежным уровням) и имеет глубину Г loga (г — /) 1.
Дерево отрезков Т(1, г) предназначено для динамического запоминания тех интервалов, чьи концы принадлежат множеству {/, /+ 1, . . ., г} (т. е. допустимы операции вставки и удаления). В частности, при г — / > 3 произвольный интервал [Ь, е] с целыми b < е будет разбит в набор из не более чем \\og2{r — — /) 1 + L log2 —/) J —2 стандартных интервалов дерева Т(1, г). Фрагментация интервала [Ь, е] полностью определяется операцией, которая заносит (вставляет) [Ь, е) в дерево отрезков Т, и, значит, обращением ВСТАВИТЬ(Ь, е; корень (Т)) к следующей процедуре:
') Строго говоря, интервал, связанный с и, это полуоткрытый интервал [B[v], E[v]), за исключением узлов самого правого пути в Т(1,г), чьи интервалы замкнуты.
tл. 1. Введение
procedure ВСТАВИТЬ(b, е; v) begin if and (?[a]<e) then назначить [b, e] узлу v
else begin if (b < \_ (B[v] + E[v])/2}) then ВСТАВИТЬ (b, e; ЛСЫЩу]); if (UB[v] + E[v])/2}<e) then ВСТАВИТЬ(6,е;ПСЫНН)
end
end.
Действие ВСТАВИТЬ(b,e; корень (T)) соответствует «маршруту» в Т, имеющему следующую общую структуру (рис. 1.2): (возможно, пустой) начальный путь, именуемый Рнач, от корня до узла v*, называемого развилкой, из которого выходят два
Рис. 1.2. Вставка интервала [74, 107] в Г(1,257). Узлы отнесения окружены дважды.
(возможно, пустых) пути—Рл и Рп. Вставляемый интервал относится или полностью к развилке (в этом случае Рл и Рп оба пусты), или ко всем правым сыновьям пути Рл. которые сами не на Рл. наряду со всеми левыми сыновьями пути Рп, которые сами не на Рп: при этом определяется фрагментация [Ь, е] (узлы отнесения).
1.2. Алгоритмические основы
27
Отнесение интервала к узлу v из Т может принимать разные формы в зависимости от потребностей конкретного приложения. Часто все, что надо знать, — это мощность множества интервалов, отнесенных к любому заданному узлу v\ ее можно запомнить в единственном неотрицательном целом параметре C[v], обозначающем эту мощность. Тогда отнесение [Ь, е] к узлу v — это всего лишь
C[v]:=C[v] + l.
В других приложениях надо сохранить сведения об интервалах, отнесенных к узлу v. Тогда к каждому узлу дерева Т добавляется вторичная структура — связный список S[v\, чьи записи являются идентификаторами этих интервалов.
Совершенно симметрична операции ВСТАВИТЬ операция УДАЛИТЬ, выражаемая следующей процедурой (здесь предполагается, что нас интересует только состояние параметра C[v]):
