Дерево диапазона

Дерево диапазона
Тип	дерево
Изобретенный	1979
Изобретён	Джон Луис Бентли
Временная сложность в обозначении большого О Операция Средний Худший случай Поиск $O(\log ^{d}n+k)$ $O(\log ^{d}n+k)$ Пространственная сложность Космос $O(n\log ^{d-1}n)$ $O(n\log ^{d-1}n)$

В информатике дерево диапазонов — это упорядоченная древовидная структура данных, содержащая список точек. обо всех точках в заданном диапазоне Он позволяет эффективно сообщать и обычно используется в двух или более измерениях. Деревья хребта были представлены Джоном Луи Бентли в 1979 году. Подобные структуры данных были независимо открыты Люкером. Ли и Вонг, и Уиллард. Дерево диапазонов является альтернативой дереву k -d . По сравнению с деревьями k -d деревья диапазонов обеспечивают более быстрое время запроса (в нотации Big O ). $O(\log ^{d}n+k)$ но хуже хранить $O(n\log ^{d-1}n)$, где n — количество точек, хранящихся в дереве, d — размерность каждой точки, а k — количество точек, сообщаемых данным запросом.

Бернар Шазель улучшил это, чтобы время запроса $O(\log ^{d-1}n+k)$ и пространственная сложность $O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)$.

Структура данных

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

Дерево диапазонов на наборе одномерных точек представляет собой сбалансированное двоичное дерево поиска по этим точкам. Точки, хранящиеся в дереве, хранятся в листьях дерева; каждый внутренний узел хранит наибольшее значение своего левого поддерева.Дерево диапазонов на множестве точек в d -размерах представляет собой рекурсивно определенное многоуровневое двоичное дерево поиска . Каждый уровень структуры данных представляет собой двоичное дерево поиска по одному из d -измерений.Первый уровень представляет собой двоичное дерево поиска по первой из d -координат. Каждая вершина v этого дерева содержит связанную структуру, которая представляет собой ( d −1)-мерное дерево диапазонов в последних ( d −1)-координатах точек, хранящихся в поддереве v .

Операции

Строительство

Одномерное дерево диапазонов на наборе из n точек — это двоичное дерево поиска, которое можно построить в $O(n\log n)$ время. Деревья диапазонов в более высоких измерениях строятся рекурсивно путем построения сбалансированного двоичного дерева поиска по первой координате точек, а затем для каждой вершины v в этом дереве строится ( d −1)-мерное дерево диапазонов по точкам, содержащимся в поддерево v . Построение дерева диапазонов таким способом потребует $O(n\log ^{d}n)$ время.

Это время построения можно сократить для двумерных деревьев диапазонов до $O(n\log n)$. Пусть S — набор из n двумерных точек. Если S содержит только одну точку, верните лист, содержащий эту точку. В противном случае постройте связанную структуру S , 1-мерное дерево диапазонов по y -координатам точек в S . Пусть x _m — медианная x -координата точек. Пусть SL _и будет набором точек с координатой x, меньшей или равной x _m, пусть SR _{большей ,} будет набором точек с координатой x, чем x _m . Рекурсивно постройте v _L 2-мерное дерево диапазонов на SL _v , и R _, 2-мерное дерево диапазонов на SR _, . Создайте вершину v с левым дочерним элементом v _L и правым дочерним элементом v _R .Если мы отсортируем точки по их координатам y в начале алгоритма и сохраним этот порядок при разделении точек по их координате x , мы сможем построить связанные структуры каждого поддерева за линейное время.Это сокращает время построения двумерного дерева диапазонов до $O(n\log n)$, а также сокращает время построения d -мерного дерева диапазонов до $O(n\log ^{d-1}n)$.

Запросы диапазона

Запрос одномерного диапазона [ x ₁ , x ₂ ]. Будут сообщены точки, хранящиеся в поддеревьях, заштрихованных серым цветом. find( x ₁ ) и find( x ₂ ) будут сообщены, если они находятся внутри интервала запроса.

Запрос диапазона в дереве диапазонов сообщает набор точек, лежащих внутри заданного интервала. Чтобы сообщить точки, которые лежат в интервале [ x ₁ , x ₂ ], мы начинаем с поиска x ₁ и x ₂ . В какой-то вершине дерева пути поиска x ₁ и x ₂ разойдутся. Пусть v _Split будет последней вершиной, общей для этих двух путей поиска. Для каждой вершины v в пути поиска от v, _{разделенного} до x ₁ , если значение, хранящееся в v, больше x ₁ , сообщите о каждой точке в правом поддереве v . Если v является листом, сообщите значение, хранящееся в v , если оно находится внутри интервала запроса. Аналогично, отчет обо всех точках, хранящихся в левых поддеревьях вершин со значениями меньше x ₂ вдоль пути поиска от v _Split до x ₂ , и отчет о листе этого пути, если он находится в пределах интервала запроса.

Поскольку дерево диапазонов представляет собой сбалансированное двоичное дерево, пути поиска к x ₁ и x ₂ имеют длину $O(\log n)$. Отчет обо всех точках, хранящихся в поддереве вершины, может быть выполнен за линейное время с использованием любого обхода дерева алгоритма . Отсюда следует, что время выполнения запроса диапазона равно $O(\log n+k)$, где k — количество точек в интервале запроса.

Запросы диапазона в d -размерах аналогичны. Вместо того, чтобы сообщать обо всех точках, хранящихся в поддеревьях путей поиска, выполните запрос ( d -1)-мерного диапазона для связанной структуры каждого поддерева. В конечном итоге будет выполнен запрос одномерного диапазона и будут получены правильные точки. Поскольку d -мерный запрос состоит из $O(\log n)$ ( d -1)-мерных запросов, отсюда следует, что время, необходимое для выполнения запроса d -мерного диапазона, равно $O(\log ^{d}n+k)$, где k — количество точек в интервале запроса. Это можно свести к $O(\log ^{d-1}n+k)$ используя вариант дробного каскадирования .

См. также

• k -d дерево
• Дерево сегментов
• Поиск диапазона

Внешние ссылки

• Деревья диапазонов и сегментов в CGAL , библиотеке алгоритмов вычислительной геометрии.
• Лекция 8: Деревья хребта , Марк ван Кревельд. Архивировано здесь .
• Деревья диапазонов с использованием PAM , параллельной расширенной библиотеки карт.
• 2D-визуализация дерева диапазонов , Чжоу Кайсюань.