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

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

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

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

• 1 Структура данных
• 2 Операции
  • 2.1 Построение
  • 2.2 Запросы диапазона
• 3 См. также
• 4 Ссылки
• 5 Внешние ссылки

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

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

Построение

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

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

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

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

A запрос диапазона в дереве диапазонов сообщает набор точки, лежащие внутри заданного интервала. Чтобы сообщить о точках, которые лежат в интервале [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 имеют длину $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$. Отчет о всех точках, хранящихся в поддереве вершины, может быть выполнен за линейное время с использованием любого алгоритма обхода дерева. Отсюда следует, что время выполнения запроса диапазона составляет $O\; (log\; \; n\; +\; k)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n\; +\; k)\}$, где k - количество точек в интервал запроса.

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

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

• Деревья диапазонов и сегментов в CGAL, Библиотека алгоритмов вычислительной геометрии.
• Лекция 8: Деревья диапазонов, Марк ван Кревельд. ​​
• Деревья диапазонов с использованием PAM, библиотеки параллельных расширенных карт.