В информатике , А дерево сегмента, также известное как дерево статистики, это дерево структура данных используются для хранения информации о интервалах или сегментах. Он позволяет запросить, какой из сохраненных сегментов содержит данную точку. В принципе, это статическая структура; то есть, это структура, которую нельзя изменить после того, как она построена. Похожая структура данных - это дерево интервалов .
Дерево сегментов для набора I из n интервалов использует память O ( n log n ) и может быть построено за время O ( n log n ). Деревья сегментов поддерживают поиск всех интервалов, содержащих точку запроса во времени O (log n + k ), где k - количество извлеченных интервалов или сегментов. [1]
Сегментное дерево применяется в области вычислительной геометрии , географических информационных систем и машинного обучения .
Дерево сегментов может быть обобщено на пространства более высокой размерности .
Описание конструкции
В этом разделе описывается структура дерева сегментов в одномерном пространстве.
Пусть S - набор интервалов или сегментов. Пусть p 1 , p 2 , ..., p m - список различных конечных точек интервала, отсортированный слева направо. Рассмотрим разбиение вещественной прямой, вызванное этими точками. Области этого разбиения называются элементарными интервалами . Таким образом, элементарные интервалы слева направо:
То есть список элементарных интервалов состоит из открытых интервалов между двумя последовательными конечными точками p i и p i +1 , чередующихся с закрытыми интервалами, состоящими из одной конечной точки. Отдельные точки рассматриваются как интервалы, потому что ответ на запрос не обязательно совпадает внутри элементарного интервала и его конечных точек. [2]
Для данного набора I интервалов или сегментов дерево сегментов T для I структурировано следующим образом:
- T - бинарное дерево .
- Его листья соответствуют элементарным интервалам, индуцированным конечными точками в I , упорядоченным образом: крайний левый лист соответствует крайнему левому интервалу и т. Д. Элементарный интервал, соответствующий листу v , обозначается Int ( v ).
- Эти внутренние узлы из Т соответствует интервалам , которые являются объединением элементарных интервалов: интервал Int ( N ) , соответствующего узлу N является объединением интервалов , соответствующих листьев дерева с корнем в N . Это означает, что Int ( N ) - это объединение интервалов двух своих дочерних элементов.
- Каждый узел или лист v в T хранит интервал Int ( v ) и набор интервалов в некоторой структуре данных. Это каноническое подмножество узла v содержит интервалы [ x , x ′ ] из I, такие что [ x , x ′ ] содержит Int ( v ) и не содержит Int (parent ( v )). То есть каждый узел в T хранит сегменты, которые охватывают его интервал, но не охватывают интервал его родителя. [3]
Требования к хранилищу
В этом разделе анализируется стоимость хранения дерева сегментов в одномерном пространстве.
Сегментное дерево T на множестве I из n интервалов использует память O ( n log n ).
Лемма - Любой интервал [ х , х ' ] из I хранится в каноническом наборе не больше двух узлов в однойтой же глубине.
Пусть v 1 , v 2 , v 3 - три узла на одной глубине, пронумерованные слева направо; и пусть p ( v ) будет родительским узлом любого заданного узла v . Предположим, что [ x , x ′ ] хранится в v 1 и v 3 . Это означает, что [ x , x ′ ] охватывает весь интервал от левой конечной точки Int ( v 1 ) до правой конечной точки Int ( v 3 ). Обратите внимание, что все сегменты на определенном уровне не перекрываются и упорядочены слева направо: это верно по конструкции для уровня, содержащего листья, и свойство не теряется при переходе с любого уровня на уровень выше, путем объединения пар смежных сегментов. Теперь либо parent ( v 2 ) = parent ( v 1 ), либо первый находится справа от последнего (ребра в дереве не пересекаются). В первом случае крайняя левая точка Int (parent ( v 2 )) совпадает с крайней левой точкой Int ( v 1 ); во втором случае крайняя левая точка Int (parent ( v 2 )) находится справа от крайней правой точки Int (parent ( v 1 )) и, следовательно, также справа от крайней правой точки Int ( v 1 ) точка. В обоих случаях Int (parent ( v 2 )) начинается в самой левой точке Int ( v 1 ) или справа от нее . Аналогичные рассуждения показывают, что Int (parent ( v 2 )) заканчивается в самой правой точке Int ( v 3 ) или слева от нее. Следовательно, Int (parent ( v 2 )) должен содержаться в [ x , x ′ ]; следовательно, [ x , x ′ ] не будет храниться в v 2 .
- Множество I имеет не более 4 n + 1 элементарных интервалов. Поскольку T - бинарное сбалансированное дерево с не более чем 4 n + 1 листом, его высота равна O (log n ). Поскольку любой интервал сохраняется не более двух раз на заданной глубине дерева, общий объем памяти равен O ( n log n ). [4]
Строительство
В этом разделе описывается построение дерева сегментов в одномерном пространстве.
Дерево сегментов из набора сегментов I можно построить следующим образом. Сначала сортируются конечные точки интервалов в I. Отсюда получаются элементарные интервалы. Затем на элементарных интервалах строится сбалансированное двоичное дерево, и для каждого узла v определяется интервал Int ( v ), который он представляет. Осталось вычислить канонические подмножества узлов. Для этого интервалы в I вставляются один за другим в дерево сегментов. Интервал X = [ x , x ′ ] может быть вставлен в поддерево с корнем в T , используя следующую процедуру: [5]
- Если Int ( T ) содержится в X, сохраните X в T и закончите.
- Еще:
- Если X пересекает интервал левого дочернего элемента T , то вставьте X в этот дочерний элемент рекурсивно.
- Если X пересекает интервал правого дочернего элемента T , то вставьте X в этот дочерний элемент рекурсивно.
Операция завершена конструкция занимает O ( п войти н ) время, п -число сегментов в I .
- Сортировка конечных точек занимает O ( n log n ). Построение сбалансированного двоичного дерева из отсортированных конечных точек занимает линейное время по n .
- Вставка интервала X = [ x , x ′ ] в дерево стоит O (log n ).
Посещение каждого узла занимает постоянное время (при условии, что канонические подмножества хранятся в простой структуре данных, такой как связанный список ). Когда мы посещаем узел V , мы либо магазин X в V , или Int ( v ) содержит конечную точку X . Как доказано выше, интервал сохраняется не более двух раз на каждом уровне дерева. Также существует не более одного узла на каждом уровне, чей соответствующий интервал содержит x , и один узел, интервал которого содержит x ' . Таким образом, посещается не более четырех узлов на каждом уровне. Поскольку существует O (log n ) уровней, общая стоимость вставки составляет O (log n ). [1]
Запрос
В этом разделе описывается операция запроса дерева сегментов в одномерном пространстве.
Запрос дерева сегментов получает точку q x (должен быть одним из листьев дерева) и извлекает список всех сохраненных сегментов, которые содержат точку q x .
Официально заявлено; учитывая узел (поддерево) v и точку запроса q x , запрос может быть выполнен с использованием следующего алгоритма:
- Report all the intervals in I(v).
- If v is not a leaf:
- If qx is in Int(left child of v) then
- Perform a query in the left child of v.
- If qx is in Int(right child of v) then
- Perform a query in the right child of v.
- If qx is in Int(left child of v) then
In a segment tree that contains n intervals, those containing a given query point can be reported in O(log n + k) time, where k is the number of reported intervals.
The query algorithm visits one node per level of the tree, so O(log n) nodes in total. On the other hand, at a node v, the segments in I are reported in O(1 + kv) time, where kv is the number of intervals at node v, reported. The sum of all the kv for all nodes v visited, is k, the number of reported segments.[4]
Обобщение для более высоких измерений
The segment tree can be generalized to higher dimension spaces, in the form of multi-level segment trees. In higher dimensional versions, the segment tree stores a collection of axis-parallel (hyper-)rectangles, and can retrieve the rectangles that contain a given query point. The structure uses O(n logd n) storage, and answers queries in O(logd n).
The use of fractional cascading lowers the query time bound by a logarithmic factor. The use of the interval tree on the deepest level of associated structures lowers the storage bound by a logarithmic factor.[6]
Заметки
A query that asks for all the intervals containing a given point is often referred as a stabbing query.[7]
The segment tree is less efficient than the interval tree for range queries in one dimension, due to its higher storage requirement: O(n log n) against the O(n) of the interval tree. The importance of the segment tree is that the segments within each node’s canonical subset can be stored in any arbitrary manner.[7]
For n intervals whose endpoints are in a small integer range (e.g., in the range [1,…,O(n)]), optimal data structures[which?] exist with a linear preprocessing time and query time O(1 + k) for reporting all k intervals containing a given query point.
Another advantage of the segment tree is that it can easily be adapted to counting queries; that is, to report the number of segments containing a given point, instead of reporting the segments themselves. Instead of storing the intervals in the canonical subsets, it can simply store the number of them. Such a segment tree uses linear storage, and requires an O(log n) query time, so it is optimal.[8]
Higher dimensional versions of the interval tree and the priority search tree do not exist; that is, there is no clear extension of these structures that solves the analogous problem in higher dimensions. But the structures can be used as associated structure of segment trees.[6]
История
The segment tree was invented by Jon Bentley in 1977; in "Solutions to Klee’s rectangle problems".[7]
Рекомендации
- ^ a b (de Berg et al. 2000, p. 227)
- ^ (de Berg et al. 2000, p. 224)
- ^ (de Berg et al. 2000, pp. 225–226)
- ^ a b (de Berg et al. 2000, p. 226)
- ^ (de Berg et al. 2000, pp. 226–227)
- ^ a b (de Berg et al. 2000, p. 230)
- ^ a b c (de Berg et al. 2000, p. 229)
- ^ (de Berg et al. 2000, pp. 229–230)
Источники цитируются
- de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000). "More Geometric Data Structures". Computational Geometry: algorithms and applications (2nd ed.). Springer-Verlag Berlin Heidelberg New York. doi:10.1007/978-3-540-77974-2. ISBN 3-540-65620-0.
- http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf
Внешние ссылки
- Segment Tree – CP-Algorithms