Дерево интервалов

В информатике дерево интервалов представляет собой древовидную структуру данных для удержания интервалов. В частности, он позволяет эффективно находить все интервалы, которые перекрываются с любым заданным интервалом или точкой. Он часто используется для оконных запросов, например, чтобы найти все дороги на компьютерной карте внутри прямоугольного окна просмотра или найти все видимые элементы внутри трехмерной сцены. Похожая структура данных - дерево сегментов .

Тривиальное решение - посетить каждый интервал и проверить, пересекает ли он заданную точку или интервал, для чего требуется $O\; (n)\; \{\backslash \; displaystyle\; O\; (n)\}$время, где $n\; \{\backslash \; displaystyle\; n\}$- количество интервалов в коллекции. Поскольку запрос может возвращать все интервалы, например, если запрос представляет собой большой интервал, пересекающий все интервалы в коллекции, это асимптотически оптимально ; однако мы можем добиться большего, если рассмотрим алгоритмы, чувствительные к выводу, где время выполнения выражается в терминах $m\; \{\backslash \; displaystyle\; m\}$, количества интервалов, создаваемых запрос. Деревья интервалов имеют время запроса $O\; (log\; \; n\; +\; m)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n\; +\; m)\}$и начальное время создания $O\; (n\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; log\; n)\}$с ограничением потребления памяти $O\; (n)\; \{\backslash \; displaystyle\; O\; (n)\}$. После создания деревья интервалов могут быть динамическими, что позволяет эффективно вставлять и удалять интервалы за $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$времени. Если конечные точки интервалов находятся в пределах небольшого целого диапазона (например, в диапазоне $[1,\dots ,\; O\; (n)]\; \{\backslash \; displaystyle\; [1,\; \backslash \; ldots,\; O\; (n)]\}$), существуют более быстрые и фактически оптимальные структуры данных со временем предварительной обработки $O\; (n)\; \{\backslash \; displaystyle\; O\; (n)\}$и временем запроса $O\; (1\; +\; m)\; \{\backslash \; displaystyle\; O\; (1\; +\; m)\}$для сообщения $m\; \{\backslash \; displaystyle\; m\}$интервалов, содержащих заданную точку запроса (см. Очень простой вариант).

• 1 Наивный подход
• 2 Центрированное дерево интервалов
  • 2.1 Построение
  • 2.2 Пересечение
    • 2.2.1 С точкой
    • 2.2.2 С интервалом
  • 2.3 Выше размеры
  • 2.4 Удаление
  • 2.5 Балансировка
• 3 Расширенное дерево
  • 3.1 Запросы членства
  • 3.2 Пример Java: добавление нового интервала к дереву
  • 3.3 Пример Java: поиск точки или интервала в дереве
  • 3.4 Более высокие измерения
• 4 Срединное или ориентированное на длину дерево
  • 4.1 Тест на перекрытие
  • 4.2 Добавление интервала
  • 4.3 Поиск всех перекрывающихся интервалов
• 5 Ссылки
• 6 Внешние ссылки

В простом случае интервалы не перекрываются, и их можно вставить в простое двоичное дерево поиска и запросить в $O\; (log\; \; п)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$время. Однако с произвольно перекрывающимися интервалами невозможно сравнить два интервала для вставки в дерево, поскольку порядок сортировки по начальным или конечным точкам может быть различным. Наивный подход может заключаться в построении двух параллельных деревьев, одно из которых упорядочено по начальной точке, а второе - по конечной точке каждого интервала. Это позволяет отбрасывать половину каждого дерева за $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$времени, но результаты должны быть объединены, что требует $O\; (n)\; \{\backslash \; displaystyle\; O\; (n)\}$время. Это дает нам запросы в $O\; (n\; +\; log\; \; n)\; =\; O\; (n)\; \{\backslash \; displaystyle\; O\; (n\; +\; \backslash \; log\; n)\; =\; O\; (n)\}$, что не лучше, чем грубый -сила.

Деревья интервалов решают эту проблему. В этой статье описываются два альтернативных дизайна для дерева интервалов, получившие название центрированного дерева интервалов и расширенного дерева.

Запросы требуют $O\; (log\; \; n\; +\; m)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n\; +\; m)\}$времени, с $n\; \{\backslash \; displaystyle\; n\}$- общее количество интервалов, а $m\; \{\backslash \; displaystyle\; m\}$- количество полученных результатов. Конструкция требует $O\; (n\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; log\; n)\}$времени, а для хранения требуется $O\; (n)\; \{\backslash \; displaystyle\; O\; (n)\}$пробел.

Построение

Учитывая набор $n\; \{\backslash \; displaystyle\; n\}$интервалов в числовой строке, мы хотим построить структуру данных, чтобы мы могли эффективно получить все интервалы, перекрывающие другой интервал или точку.

Мы начинаем с того, что берем весь диапазон всех интервалов и делим его пополам в $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$(на практике $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$следует выбрать, чтобы дерево оставалось относительно сбалансированным). Это дает три набора интервалов, полностью слева от $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, которые мы назовем $S\; left\; \{\backslash \; displaystyle\; S\_\; \{\backslash \; textrm\; \{left\}\}\}$, полностью справа от $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, которые мы назовем $S\; right\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{right\}\}\}$, и те, которые перекрывают $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$которые мы назовем $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$.

Интервалы в $S\; left\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{left\}\}\}$и $S\; right\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{right\}\}\}$рекурсивно делятся таким же образом, пока не останется никаких интервалов.

Интервалы в $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, которые перекрывают центральную точку, хранятся в отдельной структуре данных, связанной с узлом в интервальное дерево. Эта структура данных состоит из двух списков, один из которых содержит все интервалы, отсортированные по их начальным точкам, а другой - все интервалы, отсортированные по их конечным точкам.

Результатом является двоичное дерево, в котором каждый узел хранит:

• Центральная точка
• Указатель на другой узел, содержащий все интервалы полностью слева от центра. точка
• Указатель на другой узел, содержащий все интервалы полностью правее центральной точки
• Все интервалы, перекрывающие центральную точку, отсортированные по их начальной точке
• Все интервалы, перекрывающие центральная точка, отсортированная по конечной точке

Пересечение

Учитывая структуру данных, построенную выше, мы получаем запросы, состоящие из диапазонов или точек, и возвращаем все диапазоны в исходном наборе, перекрывающие этот ввод.

С точкой

Задача состоит в том, чтобы найти все интервалы в дереве, которые перекрывают заданную точку $x\; \{\backslash \; displaystyle\; x\}$. Обход дерева выполняется с помощью аналогичного рекурсивного алгоритма, который использовался бы для обхода традиционного двоичного дерева, но с дополнительной логикой для поддержки поиска интервалов, перекрывающих «центральную» точку в каждом узле.

Для каждого узла дерева $x\; \{\backslash \; displaystyle\; x\}$сравнивается с $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, средняя точка, используемая при построении узла выше. Если $x\; \{\backslash \; displaystyle\; x\}$меньше $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, крайний левый набор интервалов, $S\; left\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{left\}\}\}$, считается. Если $x\; \{\backslash \; displaystyle\; x\}$больше, чем $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, крайний правый набор интервалов, $S\; right\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{right\}\}\}$, считается.

Все интервалы в $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, которые начинаются до $x\; \{\backslash \; displaystyle\; x\}$, должны перекрываться $x\; \{\backslash \; displaystyle\; x\}$, если $x\; \{\backslash \; displaystyle\; x\}$меньше $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$.. Аналогичным образом, тот же метод применяется при проверке заданного интервала. Если заданный интервал заканчивается в y, а y меньше $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, все интервалы в $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, которые начинаются до y, также должны перекрывать заданный интервал.

Поскольку каждый узел обрабатывается, когда мы перемещаемся по дереву от корня к листу, диапазоны в его $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$обрабатываются. Если $x\; \{\backslash \; displaystyle\; x\}$меньше $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, мы знаем, что все интервалы в $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$конец после $x\; \{\backslash \; displaystyle\; x\}$, иначе они не могли перекрываться $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$. Следовательно, нам нужно найти только те интервалы в $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, которые начинаются перед $x\; \{\backslash \; displaystyle\; x\}$. Мы можем проконсультироваться со списками $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, которые уже созданы. Поскольку в этом сценарии нас интересуют только начала интервала, мы можем просмотреть список, отсортированный по началу. Предположим, мы нашли в этом списке ближайшее число, не превышающее $x\; \{\backslash \; displaystyle\; x\}$. Все диапазоны от начала списка до найденной точки перекрываются $x\; \{\backslash \; displaystyle\; x\}$, потому что они начинаются до $x\; \{\backslash \; displaystyle\; x\}$и заканчиваются после $x\; \{\backslash \; displaystyle\; x\}$(как мы знаем, потому что они перекрывают $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, который больше, чем $х\; \{\backslash \; displaystyle\; x\}$). Таким образом, мы можем просто начать перечисление интервалов в списке до тех пор, пока значение начальной точки не превысит $x\; \{\backslash \; displaystyle\; x\}$.

Аналогично, если $x\; \{\backslash \; displaystyle\; x\}$больше, чем $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, мы знаем, что все интервалы в $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$должен начинаться перед $x\; \{\backslash \; displaystyle\; x\}$, поэтому мы находим те интервалы, которые заканчиваются после $x\; \{\backslash \; displaystyle\; x\}$, используя список, отсортированный по интервалу концовки.

Если $x\; \{\backslash \; displaystyle\; x\}$точно соответствует $x\; center\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, все интервалы в $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$можно добавить к результатам без дальнейшей обработки, а обход дерева можно остановить.

С интервалом

Для интервала результатов $r\; \{\backslash \; displaystyle\; r\}$, чтобы пересечь интервал нашего запроса $q\; \{\backslash \; displaystyle\; q\}$должно выполняться одно из следующих условий:

• начальная и / или конечная точка $r\; \{\backslash \; displaystyle\; r\}$находится в $q\; \{\backslash \; displaystyle\; q\}$; или
• $r\; \{\backslash \; displaystyle\; r\}$полностью охватывает $q\; \{\backslash \; displaystyle\; q\}$.

Сначала мы находим все интервалы с начальной и / или конечной точками внутри $q\; \{\backslash \; displaystyle\; q\}$с использованием отдельно построенного дерева. В одномерном случае мы можем использовать дерево поиска, содержащее все начальные и конечные точки в наборе интервалов, каждая из которых имеет указатель на соответствующий интервал. Бинарный поиск в $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$времени для начала и конца $q\; \{\backslash \; displaystyle\; q\}$показывает минимальные и максимальные точки для рассмотрения. Каждая точка в этом диапазоне ссылается на интервал, который перекрывает $q\; \{\backslash \; displaystyle\; q\}$и добавляется в список результатов. Следует проявлять осторожность, чтобы избежать дублирования, поскольку интервал может как начинаться, так и заканчиваться в пределах $q\; \{\backslash \; displaystyle\; q\}$. Это можно сделать с помощью двоичного флага на каждом интервале, чтобы отметить, был ли он добавлен в набор результатов.

Наконец, мы должны найти интервалы, которые заключают $q\; \{\backslash \; displaystyle\; q\}$. Чтобы найти их, мы выбираем любую точку внутри $q\; \{\backslash \; displaystyle\; q\}$и используем описанный выше алгоритм, чтобы найти все интервалы, пересекающие эту точку (опять же, стараясь удалить дубликаты).

Более высокие измерения

Структура данных интервального дерева может быть обобщена до более высокого измерения $N\; \{\backslash \; displaystyle\; N\}$с идентичным временем запроса и построения и $О\; (n\; журнал\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; log\; n)\}$пробел.

Сначала создается дерево диапазонов в измерениях $N\; \{\backslash \; displaystyle\; N\}$, которое позволяет эффективно извлекать все интервалы с начальной и конечной точками внутри область запроса $R\; \{\backslash \; displaystyle\; R\}$. После того, как соответствующие диапазоны найдены, остается только те диапазоны, которые охватывают область в некотором измерении. Чтобы найти эти перекрытия, создаются деревья интервалов $N\; \{\backslash \; displaystyle\; N\}$, и для каждого из них запрашивается одна ось, пересекающая $R\; \{\backslash \; displaystyle\; R\}$. Например, в двух измерениях нижняя часть квадрата $R\; \{\backslash \; displaystyle\; R\}$(или любой другой горизонтальной линии, пересекающей $R\; \{\backslash \; displaystyle\; R\}$) будет запрашиваться в дереве интервалов, построенном для горизонтальной оси. Точно так же левая сторона (или любая другая вертикальная линия, пересекающая $R\; \{\backslash \; displaystyle\; R\}$) будет опрошена по дереву интервалов, построенному на вертикальной оси.

Каждое дерево интервалов также нуждается в добавлении для более высоких измерений. В каждом узле, который мы просматриваем в дереве, $x\; \{\backslash \; displaystyle\; x\}$сравнивается с $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$найти совпадения. Вместо двух отсортированных списков точек, которые использовались в одномерном случае, строится дерево диапазонов. Это позволяет эффективно извлекать все точки в $S\; center\; \{\backslash \; displaystyle\; S\; \_\; \{\backslash \; textrm\; \{center\}\}\}$, которая перекрывает область $R\; \{\backslash \; displaystyle\; R\}$.

Удаление

Если после удаления интервала из дерева узел, содержащий этот интервал, больше не содержит интервалов, этот узел может быть удален из дерева. Это сложнее, чем обычная операция удаления двоичного дерева.

Интервал может перекрывать центральную точку нескольких узлов в дереве. Поскольку каждый узел хранит интервалы, которые перекрывают его, причем все интервалы полностью находятся слева от его центральной точки в левом поддереве, аналогично для правого поддерева, из этого следует, что каждый интервал хранится в узле, ближайшем к корню из набора узлы, центральная точка которых перекрывается.

Обычные операции удаления в двоичном дереве (для случая, когда удаляемый узел имеет двух дочерних узлов) включают продвижение узла дальше от листа до позиции удаляемого узла (обычно крайний левый дочерний элемент справа поддерево или крайний правый дочерний элемент левого поддерева).

Удаление узла с двумя дочерними элементами из двоичного дерева поиска с использованием упорядоченного предшественника (крайний правый узел в левом поддереве, помеченный 6).

В результате этого продвижения некоторые узлы, которые находились над повышенным узлом, станут его потомков; необходимо найти в этих узлах интервалы, которые также перекрывают продвинутый узел, и переместить эти интервалы в продвинутый узел. Как следствие, это может привести к появлению новых пустых узлов, которые должны быть удалены снова по тому же алгоритму.

Балансировка

Те же проблемы, которые влияют на удаление, также влияют на операции вращения; вращение должно сохранять инвариант, что узлы хранятся как можно ближе к корню.

Расширенное дерево с низким значением в качестве ключа и максимальным высоким в качестве дополнительной аннотации. Например, при проверке, перекрывает ли данный интервал [40, 60) интервалы в дереве, показанном выше, мы видим что он не перекрывает интервал [20, 36) в корне, но поскольку t Если низкое значение корня (20) меньше искомого высокого значения (60), мы должны искать правое поддерево. Максимальное значение 41 для левого поддерева превышает искомое минимальное значение (40), поэтому мы также должны искать в левом поддереве. Однако оба потомка узла [3, 41) имеют максимальные максимумы меньше 40, поэтому поиск левого поддерева на этом заканчивается, и нет необходимости искать их.

Другой способ представления интервалов описан в Cormen и другие. (2009, Раздел 14.3: Деревья интервалов, стр. 348–354).

И вставка, и удаление требуют $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$времени, с $n\; \{\backslash \; displaystyle\; n\}$- общее количество интервалов в дереве до операции вставки или удаления.

Расширенное дерево может быть построено из простого упорядоченного дерева, например, двоичного дерева поиска или самобалансирующегося двоичного дерева поиска, упорядоченного по 'младшему' значения интервалов. Затем к каждому узлу добавляется дополнительная аннотация, в которой записывается максимальное верхнее значение среди всех интервалов, начиная с этого узла. Поддержание этого атрибута включает обновление всех предков узла снизу вверх всякий раз, когда узел добавляется или удаляется. Это занимает всего O (h) шагов на добавление или удаление узла, где h - высота узла, добавленного или удаленного в дереве. Если есть какие-либо вращения дерева во время вставки и удаления, затронутые узлы также могут нуждаться в обновлении.

Теперь известно, что два интервала $A\; \{\backslash \; displaystyle\; A\}$и $B\; \{\backslash \; displaystyle\; B\}$перекрываются только тогда, когда оба $A\; низкий\; \le \; B\; высокий\; \{\backslash \; displaystyle\; A\; \_\; \{\backslash \; textrm\; \{low\}\}\; \backslash \; leq\; B\; \_\; \{\backslash \; textrm\; \{high\}\}\}$и $A\; высокий\; \ge \; B\; низкий\; \{\backslash \; displaystyle\; A\; \_\; \{\backslash \; textrm\; \{high\}\}\; \backslash \; geq\; B\; \_\; \{\backslash \; textrm\; \{low\}\}\}$. При поиске в деревьях узлов, перекрывающихся с заданным интервалом, вы можете сразу же пропустить:

• все узлы справа от узлов, нижнее значение которых превышает конец заданного интервала.
• все узлы, у которых есть свои максимальное максимальное значение ниже начала данного интервала.

Запросы членства

Некоторая производительность может быть получена, если дерево избегает ненужных обходов. Это может происходить при добавлении уже существующих интервалов или удалении несуществующих интервалов.

Общий порядок интервалов можно определить, упорядочив их сначала по нижним границам, а затем по верхним границам. Затем проверка принадлежности может быть выполнена за $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$времени по сравнению с $O\; (k\; +\; log\; \; n)\; \{\; \backslash \; displaystyle\; O\; (k\; +\; \backslash \; log\; n)\}$время, необходимое для поиска дубликатов, если $k\; \{\backslash \; displaystyle\; k\}$интервалы перекрывают интервал, который нужно вставить или удалить. Это решение имеет то преимущество, что не требует дополнительных конструкций. Изменение строго алгоритмическое. Недостатком является то, что запросы о членстве занимают $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$времени.

В качестве альтернативы, со скоростью $O\; (n)\; \{\backslash \; displaystyle\; O\; (n)\}$памяти, запросы членства в ожидаемое постоянное время могут быть реализованы с помощью хэш-таблицы, обновленной в ногу с интервальным деревом. Это не обязательно может удвоить общую потребность в памяти, если интервалы хранятся по ссылке, а не по значению.

Пример Java: добавление нового интервала к дереву

Ключом каждого узла является сам интервал, поэтому узлы упорядочиваются сначала по низкому значению и, наконец, по большому значению, а значение каждый узел является конечной точкой интервала:

public void add (Interval i) {put (i, i.getEnd ()); }

Пример Java: поиск точки или интервала в дереве

Для поиска интервала необходимо пройти по дереву, используя ключ (n.getKey ()) и высокое значение (n.getValue ()) для исключения ветвей, которые не могут перекрывать запрос. Самый простой случай - это точечный запрос:

// Поиск всех интервалов, содержащих «p», начиная с // узла «n» и добавляя соответствующие интервалы в список «result» public void search (IntervalNode n, Point p, List result) {// Не искать узлы, которые не существуют if (n == null) return; // Если p находится справа от крайней правой точки любого интервала // в этом узле и во всех дочерних узлах, совпадений не будет. если (p.compareTo (n.getValue ())>0) return; // Поиск левых дочерних элементов search (n.getLeft (), p, result); // Проверяем этот узел if (n.getKey (). Contains (p)) result.add (n.getKey ()); // Если p находится слева от начала этого интервала, // тогда он не может быть ни в одном дочернем элементе справа. if (p.compareTo (n.getKey (). getStart ()) < 0) return; // Otherwise, search right children search(n.getRight(), p, result); }

где

a.compareTo (b)возвращает отрицательное значение, если < b

a.compareTo (b)возвращает ноль, если a = b

a.compareTo (b)возвращает положительное значение, если a>b

Код для поиска интервала аналогичен, за исключением проверки посередине:

// Проверяем этот узел, если (n.getKey (). OverlapsWith (i)) result.add (n.getKey ());

overlapsWith ()определяется как:

public boolean overlapsWith (Interval other) {return start.compareTo (other.getEnd ()) <= 0 end.compareTo(other.getStart())>= 0;}

Более высокие измерения

Расширенные деревья можно расширить до более высоких измерений, циклически перебирая измерения на каждом уровне дерево. Например, для двух измерений нечетные уровни дерева могут содержать диапазоны для координаты x, а четные уровни содержат диапазоны для координаты Y. Этот подход эффективно преобразует структуру данных из расширенного двоичного дерева в расширено kd-tree, что значительно усложняет алгоритмы балансировки для i вставки и удаления.

Более простое решение - использовать вложенные деревья интервалов. Сначала создайте дерево, используя диапазоны для координаты y. Теперь для каждого узла в дереве добавьте другое дерево интервалов в диапазонах x для всех элементов, диапазон y которых совпадает с диапазоном y этого узла.

Преимущество этого решения заключается в том, что его можно расширить до произвольного количества измерений с использованием той же кодовой базы.

Поначалу дополнительные затраты на вложенные деревья могут показаться непомерно высокими, но обычно это не так. Как и в случае с ранее не вложенным решением, для каждой координаты x требуется один узел, что дает одинаковое количество узлов для обоих решений. Единственные дополнительные накладные расходы - это вложенные древовидные структуры, по одной на вертикальный интервал. Эта структура обычно имеет незначительный размер и состоит только из указателя на корневой узел и, возможно, количества узлов и глубины дерева.

Медиальное или ориентированное на длину дерево похоже на расширенное дерево, но симметрично, с двоичным деревом поиска, упорядоченным по средним точкам интервалов. В каждом узле имеется ориентированная на максимум двоичная куча, упорядоченная по длине интервала (или половине длины). Также мы храним минимальное и максимальное возможное значение поддерева в каждом узле (таким образом, симметрия).

Тест на перекрытие

Использование только начального и конечного значений двух интервалов $(ai,\; bi)\; \{\backslash \; displaystyle\; \backslash \; left\; (a\_\; \{i\},\; b\_\; \{i\}\; \backslash \; right)\}$, для $i\; =\; 0,\; 1\; \{\backslash \; displaystyle\; i\; =\; 0,1\}$тест на перекрытие можно выполнить следующим образом:

и $a\; 1>b\; 0\; \{\backslash \; displaystyle\; a\_\; \{1\}>b\_\; \{0\}\}$

Это можно упростить, используя сумму и разницу:

$si\; =\; ai\; +\; bi\; \{\backslash \; displaystyle\; s\_\; \{i\}\; =\; a\_\; \{i\}\; +\; b\_\; \{i\}\}$

$di\; =\; bi\; -\; ai\; \{\backslash \; displaystyle\; d\_\; \{i\}\; =\; b\_\; \{i\}\; -a\_\; \{i\}\}$

Что сокращает тест на перекрытие до :

Добавление интервала

Добавление новых интервалов в дерево такое же, как для двоичного дерева поиска с использованием среднего значения в качестве ключа. Мы нажимаем $di\; \{\backslash \; displaystyle\; d\_\; \{i\}\}$в двоичную кучу, связанную с узлом, и обновить минимальное и максимальное возможные значения, связанные с все высшие узлы.

Поиск всех перекрывающихся интервалов

Давайте использовать $aq,\; bq,\; mq,\; dq\; \{\backslash \; displaystyle\; a\_\; \{q\},\; b\_\; \{q\},\; m\_\; \{q\},\; d\_\; \{q\}\; \}\}$для интервала запроса и $M\; n\; \{\backslash \; displaystyle\; M\_\; \{n\}\}$для ключа узла (по сравнению с $mi\; \{\backslash \; displaystyle\; m\_\; \{i\}\}$интервалов)

Начиная с корневого узла, в каждом узле сначала мы проверяем, возможно ли, что наш интервал запроса перекрывается с поддеревом узла, используя минимальные и максимальные значения узел (если это не так, мы не продолжим для этого узла).

Затем мы вычисляем $min\; \{di\}\; \{\backslash \; displaystyle\; \backslash \; min\; \backslash \; left\; \backslash \; \{d\_\; \{i\}\; \backslash \; right\; \backslash \}\}$для интервалов внутри этого узла (не его дочерних элементов) для перекрытия с интервалом запроса (зная $mi\; =\; M\; n\; \{\backslash \; displaystyle\; m\_\; \{i\}\; =\; M\_\; \{n\}\}$):

$min\; \{di\}\; =\; |\; m\; q\; -\; M\; n\; |\; -\; dq\; \{\backslash \; displaystyle\; \backslash \; min\; \backslash \; left\; \backslash \; \{d\_\; \{i\}\; \backslash \; right\; \backslash \}\; =\; \backslash \; left\; |\; m\_\; \{q\}\; -M\_\; \{n\}\; \backslash \; right\; |\; -d\_\; \{q\}\}$

и выполнить запрос на его двоичная куча для $di\; \{\backslash \; displaystyle\; d\_\; \{i\}\}$больше, чем $min\; \{di\}\; \{\backslash \; displaystyle\; \backslash \; min\; \backslash \; left\; \backslash \; \{d\_\; \{i\}\; \backslash \; right\; \backslash \}\; \}$

Затем мы проходим через правые и левые потомки узла, делая то же самое.

В худшем случае мы должны сканировать все узлы двоичного дерева поиска, но, поскольку запрос двоичной кучи является оптимальным, это приемлемо (двумерная задача не может быть оптимальной в обоих измерениях)

Ожидается, что этот алгоритм будет быстрее, чем традиционное дерево интервалов (расширенное дерево) для операций поиска. На практике добавление элементов происходит немного медленнее, хотя порядок увеличения такой же.

1. ^. Задачи с интервальным колющим ударом в малых целых диапазонах. ДОИ. ISAAC'09, 2009
2. ^Диапазон запросов # Операторы полугруппы

• Марк де Берг, Марк ван Кревельд, Марк Овермарс и Отфрид Шварцкопф. Вычислительная геометрия, второе исправленное издание. Springer-Verlag 2000. Раздел 10.1: Interval Trees, стр. 212–217.
• Кормен, Томас Х. ; Лейзерсон, Чарльз Э. ; Ривест, Рональд Л. ; Стейн, Клиффорд (2009), Введение в алгоритмы (3-е изд.), MIT Press и McGraw-Hill, ISBN 978-0-262 -03384-8
• Франко П. Препарата и Майкл Ян Шамос. Вычислительная геометрия: Введение. Springer-Verlag, 1985

• CGAL: Библиотека алгоритмов вычислительной геометрии на C ++ содержит надежную реализацию Range Trees
• Boost.Icl предлагает реализации C ++ наборов интервалов и карт.
• IntervalTree (Python) - центрированное дерево интервалов с балансировкой AVL, совместимое с тегированными интервалами
• Interval Tree (C #) - расширенное дерево интервалов с AVL-балансировкой
• Interval Tree (Ruby) - центрированное дерево интервалов, неизменяемое, совместимое с тегированными интервалами
• IntervalTree (Java) - расширенное дерево интервалов, с балансировкой AVL, поддерживающее перекрытие, поиск, интерфейс коллекции, интервалы, связанные с идентификатором