Введение
В информатике, дерево интервалов — это структура данных в виде дерева, предназначенная для хранения интервалов. В частности, она позволяет эффективно находить все интервалы, пересекающиеся с заданным интервалом или точкой. Часто используется для запросов, связанных с окнами, например, для поиска всех дорог на цифровой карте внутри прямоугольной области просмотра или для поиска всех видимых элементов в трехмерной сцене. Похожей структурой данных является сегментное дерево. Наивное решение заключается в переборе каждого интервала и проверке его пересечения с заданной точкой или интервалом, что требует времени, где — количество интервалов в коллекции. Поскольку запрос может вернуть все интервалы (например, если запрос представляет собой большой интервал, пересекающий все интервалы в коллекции), это асимптотически оптимально. Однако можно добиться лучших результатов, используя алгоритмы, чувствительные к объему вывода, где время выполнения выражается через , количество интервалов, возвращенных запросом. Деревья интервалов обеспечивают время запроса и время создания , ограничивая потребление памяти до . После создания деревья интервалов могут быть динамическими, позволяя эффективно вставлять и удалять интервалы за время . Если конечные точки интервалов лежат в небольшом целочисленном диапазоне (например, в диапазоне ), существуют более быстрые и, фактически, оптимальные структуры данных со временем предварительной обработки и временем запроса для поиска интервалов, содержащих заданную точку запроса (см. для очень простого примера).
In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three dimensional scene. A similar data structure is the segment tree. The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires time, where is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, we can do better by considering output sensitive algorithms, where the runtime is expressed in terms of , the number of intervals produced by the query. Interval trees have a query time of and an initial creation time of , while limiting memory consumption to After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in time. If the endpoints of intervals are within a small integer range (e. g., in the range ), faster and in fact optimal data structures exist with preprocessing time and query time for reporting intervals containing a given query point (see for a very simple one).
Наивный подход
В простом случае интервалы не перекрываются, и их можно вставить в обычное двоичное дерево поиска и выполнять запросы за время . Однако, при произвольном перекрытии интервалов, невозможно сравнить два интервала для вставки в дерево, так как сортировки по начальным или конечным точкам могут давать разные результаты. Наивный подход может заключаться в построении двух параллельных деревьев: одно, упорядоченное по начальной точке, и другое – по конечной точке каждого интервала. Это позволяет отсечь половину каждого дерева за время , но результаты необходимо объединить, что требует времени . В итоге, запросы выполняются за , что не лучше, чем полный перебор. Интервальные деревья решают эту проблему. В данной статье описываются две альтернативные реализации интервального дерева, названные централизованным интервальным деревом и дополненным деревом.
Центровое дерево интервала
Запросы требуют времени, где – общее количество интервалов, а – количество сообщенных результатов. Построение требует времени, а хранение – места.
Пересекающиеся
Учитывая построенную выше структуру данных, мы получаем запросы, состоящие из диапазонов или отдельных точек, и возвращаем все диапазоны из исходного набора, которые пересекаются с заданным запросом.
С точкой
Задача состоит в том, чтобы найти все интервалы в дереве, которые пересекаются с заданной точкой. Дерево обходится с помощью аналогичного рекурсивного алгоритма, как при обходе традиционного двоичного дерева, но с дополнительной логикой для поддержки поиска интервалов, перекрывающих "центральную" точку в каждом узле. Для каждого узла дерева значение `x` сравнивается со значением `m`, средней точкой, использованной при построении узла выше. Если `x` меньше `m`, рассматривается самый левый набор интервалов, `left`. Если `x` больше `m`, рассматривается самый правый набор интервалов, `right`. По мере обработки каждого узла при обходе дерева от корня к листу, обрабатываются диапазоны в его `intervals`. Если `x` меньше `m`, мы знаем, что все интервалы в `intervals` заканчиваются после `x`, иначе они не могли бы также пересекаться с `x`. Поэтому нам нужно найти только те интервалы в `intervals`, которые начинаются до `x`. Мы можем обратиться к спискам `starts`, которые уже были построены. Поскольку в этом сценарии нас интересуют только начала интервалов, мы можем обратиться к списку, отсортированному по началам. Предположим, мы находим ближайшее число, не превышающее `x`, в этом списке. Все диапазоны от начала списка до найденной точки пересекаются, потому что они начинаются до `x` и заканчиваются после `x` (как мы знаем, потому что они пересекаются с `m`, которое больше `x`). Таким образом, мы можем просто начать перечислять интервалы в списке, пока значение начальной точки не превысит `x`. Аналогично, если `x` больше `m`, мы знаем, что все интервалы в `intervals` должны начинаться до `m`, поэтому мы находим те интервалы, которые заканчиваются после `m`, используя список, отсортированный по окончаниям интервалов. Если `x` точно совпадает с `m`, все интервалы в `intervals` можно добавить к результатам без дальнейшей обработки, и обход дерева можно остановить.
Likewise, if is greater than , we know that all intervals in must begin before , so we find those intervals that end after using the list sorted by interval endings. If exactly matches , all intervals in can be added to the results without further processing and tree traversal can be stopped.
Более высокие размеры
Структура данных интервального дерева может быть обобщена на большее число измерений с сохранением времени запроса и построения, а также объёма памяти. Сначала строится дерево отрезков в *d* измерениях, которое позволяет эффективно извлекать все интервалы с начальной и конечной точками внутри области запроса. После того, как соответствующие отрезки найдены, остаются только те, которые охватывают область в некотором измерении. Для поиска этих пересечений создаются интервальные деревья, и для каждого из них выполняется запрос по одной пересекающей оси. Например, в двух измерениях нижняя сторона квадрата (или любая другая горизонтальная линия, пересекающая область) будет запрошена к интервальному дереву, построенному для горизонтальной оси. Аналогично, левая сторона (или любая другая вертикальная линия, пересекающая область) будет запрошена к интервальному дереву, построенному для вертикальной оси. Каждому интервальному дереву также требуется дополнение для более высоких измерений. На каждом узле, который мы обходим в дереве, координата *x* сравнивается с координатой *y* для поиска пересечений. Вместо двух отсортированных списков точек, как в одномерном случае, строится дерево отрезков. Это позволяет эффективно извлекать все точки в области пересечения.
Удаление
Если после удаления интервала из дерева узел, содержащий этот интервал, больше не содержит интервалов, этот узел можно удалить из дерева. Это сложнее, чем обычное удаление узла в двоичном дереве. Интервал может перекрывать центральную точку нескольких узлов в дереве. Поскольку каждый узел хранит интервалы, которые его перекрывают, при этом все интервалы, полностью лежащие слева от его центральной точки, находятся в левом поддереве, а аналогично – в правом поддереве, следует, что каждый интервал хранится в узле, ближайшем к корню из множества узлов, центральную точку которых он перекрывает. Обычные операции удаления в двоичном дереве (в случае, когда удаляемый узел имеет двух потомков) включают перемещение узла, более удаленного от листа, на позицию удаляемого узла (обычно самый левый потомок правого поддерева или самый правый потомок левого поддерева). В результате этого перемещения некоторые узлы, которые находились выше перемещенного узла, станут его потомками; необходимо проверить эти узлы на наличие интервалов, которые также перекрывают перемещенный узел, и переместить эти интервалы в перемещенный узел. В результате этого могут появиться новые пустые узлы, которые необходимо удалить, повторно применив тот же алгоритм.
Балансирование
Те же проблемы, которые возникают при удалении, актуальны и для операций поворота; поворот должен обеспечивать сохранение инварианта, согласно которому узлы хранятся как можно ближе к корню.
Увеличенное дерево
Другой способ представления интервалов описан в [название раздела]. Как вставка, так и удаление требуют времени, где – общее количество интервалов в дереве до операции вставки или удаления. Увеличенное дерево может быть построено из простого упорядоченного дерева, например, двоичного дерева поиска или самобалансирующегося двоичного дерева поиска, упорядоченного по "нижним" значениям интервалов. К каждому узлу затем добавляется дополнительная информация, фиксирующая максимальное верхнее значение среди всех интервалов от этого узла и ниже. Поддержание этого атрибута включает обновление всех предков узла снизу вверх при добавлении или удалении узла. Это занимает только O(h) шагов на добавление или удаление каждого узла, где h – высота добавленного или удаленного узла в дереве. Если во время вставки и удаления происходят вращения дерева, то может потребоваться обновление и затронутых узлов. Известно, что два интервала и перекрываются только тогда, когда одновременно и . При поиске в дереве узлов, перекрывающихся с заданным интервалом, можно сразу пропускать: все узлы справа от узлов, у которых нижнее значение больше конца заданного интервала; все узлы, у которых максимальное верхнее значение меньше начала заданного интервала.
Both insertion and deletion require time, with being the total number of intervals in the tree prior to the insertion or deletion operation. An augmented tree can be built from a simple ordered tree, for example a binary search tree or self balancing binary search tree, ordered by the 'low' values of the intervals. An extra annotation is then added to every node, recording the maximum upper value among all the intervals from this node down. Maintaining this attribute involves updating all ancestors of the node from the bottom up whenever a node is added or deleted. This takes only O(h) steps per node addition or removal, where h is the height of the node added or removed in the tree. If there are any tree rotations during insertion and deletion, the affected nodes may need updating as well. Now, it is known that two intervals and overlap only when both and When searching the trees for nodes overlapping with a given interval, you can immediately skip:
all nodes to the right of nodes whose low value is past the end of the given interval. all nodes that have their maximum high value below the start of the given interval.
Запросы о членстве
Некоторая оптимизация производительности может быть достигнута, если дерево избегает ненужных обходов. Это может происходить при добавлении интервалов, которые уже существуют, или при попытке удалить интервалы, которых нет. На интервалах можно определить полный порядок, сначала упорядочив их по нижним границам, а затем по верхним границам. Тогда проверка на наличие интервала может быть выполнена за время O(log n), в отличие от времени O(n), необходимого для поиска дубликатов, если интервалы перекрываются с интервалом, который нужно вставить или удалить. Это решение имеет преимущество, заключающееся в отсутствии необходимости в дополнительных структурах данных. Изменение носит исключительно алгоритмический характер. Недостатком является то, что запросы на проверку наличия занимают время O(log n). В качестве альтернативы, при затратах памяти O(n), запросы на проверку наличия могут быть реализованы с использованием хеш-таблицы, обновляемой синхронно с интервальным деревом, со средним временем ответа, близким к константе. Это не обязательно приведет к удвоению общего объема требуемой памяти, если интервалы хранятся по ссылкам, а не по значению.
Более высокие размеры
Увеличенные деревья могут быть расширены до более высоких размерностей, последовательно перебирая размерности на каждом уровне дерева. Например, для двух размерностей нечетные уровни дерева могут содержать диапазоны для координаты x, а четные уровни – диапазоны для координаты y. Этот подход фактически преобразует структуру данных из расширенного двоичного дерева в расширенное kd-дерево, что значительно усложняет алгоритмы балансировки при вставке и удалении. Более простое решение – использовать вложенные интервальные деревья. Сначала создайте дерево, используя диапазоны для координаты y. Затем, для каждого узла в этом дереве, добавьте другое интервальное дерево для диапазонов x для всех элементов, чей y-диапазон совпадает с y-диапазоном данного узла. Преимущество этого решения заключается в том, что его можно расширить до произвольного числа размерностей, используя ту же кодовую базу. Поначалу дополнительная стоимость вложенных деревьев может показаться значительной, но обычно это не так. Как и в случае с не вложенным решением, описанным ранее, требуется один узел на каждую x-координату, что обеспечивает одинаковое количество узлов для обоих решений. Единственная дополнительная накладка – это структуры вложенных деревьев, по одной на каждый вертикальный интервал. Эта структура обычно имеет незначительный размер и состоит только из указателя на корневой узел и, возможно, количества узлов и глубины дерева.
Средне- или длиноориентированное дерево
Медиальное или ориентированное по длине дерево подобно расширенному дереву, но симметрично, при этом бинарное дерево поиска упорядочено по медианам интервалов. В каждом узле содержится максимальная ориентированная двоичная куча, упорядоченная по длине интервала (или половине его длины). Также в каждом узле мы храним минимальное и максимальное возможное значение поддерева, что обеспечивает симметрию.
Добавление интервала
Добавление новых интервалов в дерево аналогично добавлению в двоичное дерево поиска, где в качестве ключа используется медиана. Мы добавляем интервал в бинарную кучу, связанную с узлом, и обновляем минимальные и максимальные возможные значения, связанные со всеми предками этого узла.