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

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

В 1990 году Бернар Шазелл усовершенствовал этот метод, чтобы сделать запрос по сложности времени и пространства . [5] [6] O ( log d − 1 ⁡ n + k ) {\displaystyle O(\log ^{d-1}n+k)} O ( n ( log ⁡ n log ⁡ log ⁡ n ) d − 1 ) {\displaystyle O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)}

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

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

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

Операции

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

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

Это время построения может быть улучшено для 2-мерных деревьев диапазонов до . [7] Пусть S будет набором из n 2-мерных точек. Если S содержит только одну точку, вернуть лист, содержащий эту точку. В противном случае построить связанную структуру S , 1-мерное дерево диапазонов по y -координатам точек в S . Пусть x m будет медианной x -координатой точек. Пусть S L будет набором точек с x -координатой, меньшей или равной x m , и пусть S R будет набором точек с x -координатой, большей x m . Рекурсивно построить v L , 2-мерное дерево диапазонов на S L , и v R , 2-мерное дерево диапазонов на S R . Создать вершину v с левым потомком v L и правым потомком v R . Если мы отсортируем точки по их y -координатам в начале алгоритма и сохраним этот порядок при разделении точек по их x -координате, мы можем построить связанные структуры каждого поддерева за линейное время. Это сокращает время построения двумерного дерева диапазонов до , а также сокращает время построения d -мерного дерева диапазонов до . O ( n log ⁡ n ) {\displaystyle O(n\log n)} O ( n log ⁡ n ) {\displaystyle O(n\log n)} O ( n log d − 1 ⁡ n ) {\displaystyle O(n\log ^{d-1}n)}

Диапазон запросов

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

Запрос диапазона на дереве диапазонов сообщает набор точек, которые лежат внутри заданного интервала. Чтобы сообщить точки, которые лежат в интервале [ x 1 , x 2 ], мы начинаем с поиска x 1 и x 2 . В некоторой вершине дерева пути поиска к x 1 и x 2 будут расходиться. Пусть v split будет последней вершиной, которая является общей для этих двух путей поиска. Для каждой вершины v на пути поиска от v split до x 1 , если значение, сохраненное в v, больше x 1 , сообщить каждую точку в правом поддереве v . Если v является листом, сообщить значение, сохраненное в v , если оно находится внутри интервала запроса. Аналогично, сообщая все точки, сохраненные в левых поддеревьях вершин со значениями меньше x 2 вдоль пути поиска от v split до x 2 , и сообщить лист этого пути, если он находится внутри интервала запроса.

Поскольку дерево диапазонов является сбалансированным бинарным деревом, пути поиска к x 1 и x 2 имеют длину . Отчет обо всех точках, хранящихся в поддереве вершины, может быть выполнен за линейное время с использованием любого алгоритма обхода дерева . Из этого следует, что время выполнения запроса диапазона составляет , где k — количество точек в интервале запроса. O ( log ⁡ n ) {\displaystyle O(\log n)} O ( log ⁡ n + k ) {\displaystyle O(\log n+k)}

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

Смотрите также

Ссылки

  1. ^ Бентли, Дж. Л. (1979). «Разложимые задачи поиска» (PDF) . Information Processing Letters . 8 (5): 244–251. doi :10.1016/0020-0190(79)90117-0. Архивировано из оригинала 24 сентября 2017 г.
  2. ^ ab Lueker, GS (1978). "Структура данных для ортогональных диапазонных запросов". 19-й ежегодный симпозиум по основам компьютерной науки (sfcs 1978) . стр. 28–21. doi :10.1109/SFCS.1978.1. S2CID  14970942.
  3. ^ Ли, Д.Т.; Вонг, К.К. (1980). «Пятёрочные деревья: файловая структура для многомерных систем баз данных». ACM Transactions on Database Systems . 5 (3): 339. doi :10.1145/320613.320618. S2CID  2547376.
  4. ^ ab Willard, Dan E. Алгоритм супер- b -дерева (Технический отчет). Кембридж, Массачусетс: Aiken Computer Lab, Гарвардский университет. TR-03-79.
  5. ^ Шазелл, Бернард (1990). «Нижние границы для поиска в ортогональном диапазоне: I. Случай отчетности» (PDF) . Журнал ACM . 37 (2): 200–212. doi :10.1145/77600.77614. S2CID  8895683.
  6. ^ Шазелл, Бернард (1990). "Нижние границы для поиска в ортогональном диапазоне: II. Арифметическая модель" (PDF) . Журнал ACM . 37 : 439–463. doi :10.1145/79147.79149. S2CID  15935619.
  7. ^ Аб де Берг, Марк; Чеонг, Отфрид; ван Кревелд, Марк; Овермарс, Марк (2008). Вычислительная геометрия . дои : 10.1007/978-3-540-77974-2. ISBN 978-3-540-77973-5.
  • Деревья диапазонов и сегментов в CGAL , библиотеке алгоритмов вычислительной геометрии.
  • Лекция 8: Деревья на хребте, Марк ван Кревельд. ​​Архивировано здесь.
  • Деревья диапазонов с использованием PAM , параллельной дополненной библиотеки карт.
  • Визуализация 2D-дерева диапазонов, Чжоу Кайсюань.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Range_tree&oldid=1239516617"