Дерево сегментов
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
В информатике дерево сегментов — это структура данных , используемая для хранения информации об интервалах или сегментах. Это позволяет узнать, какой из сохраненных сегментов содержит данную точку. Аналогичная структура данных — дерево интервалов .
Дерево сегментов для набора I из n интервалов использует память O ( n log n ) и может быть построено за время O ( n log n ). Деревья сегментов поддерживают поиск всех интервалов, содержащих точку запроса во времени O (log n + k ), где k — количество полученных интервалов или сегментов. [1]
Приложения дерева сегментов находятся в областях вычислительной геометрии , географических информационных систем и машинного обучения .
Дерево сегментов можно обобщить на пространства более высокой размерности .
Определение [ править ]
Описание [ править ]
Пусть I — набор интервалов или сегментов. Пусть p 1 , p 2 , ..., pm — список различных конечных точек интервала, отсортированный слева направо. Рассмотрим разбиение реальной линии, вызванное этими точками. Области этого разбиения называются элементарными интервалами . Таким образом, элементарные интервалы слева направо:
![{\displaystyle (-\infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{2},p_{2}], \dots ,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+\infty )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7d38ca3ad16c39bc9f67a6e0601c8e82ff59358)
список элементарных интервалов состоит из открытых интервалов между двумя последовательными конечными точками pi То есть и pi , +1 чередующихся с закрытыми интервалами, состоящими из одной конечной точки. Отдельные точки сами по себе рассматриваются как интервалы, поскольку ответ на запрос не обязательно совпадает внутри элементарного интервала и его конечных точек. [2]
Учитывая набор I интервалов или сегментов, дерево сегментов T для I структурируется следующим образом:
- T — двоичное дерево .
- Его листья соответствуют элементарным интервалам, индуцированным конечными точками I упорядоченным образом : самый левый лист соответствует самому левому интервалу и так далее. Элементарный интервал, соответствующий листу v, обозначается Int( v ).
- Внутренние узлы T собой объединение интервалов , соответствуют интервалам, которые являются объединением элементарных интервалов: интервал Int( N ), соответствующий узлу N, соответствующих листьям дерева с корнем в N. представляет Это означает, что Int( N ) представляет собой объединение интервалов двух своих дочерних элементов.
- Каждый узел или лист v в T хранит интервал Int( v ) и набор интервалов в некоторой структуре данных. Это каноническое подмножество узла v содержит интервалы [ x , x′ ] из I такие, что [ x , x′ ] содержит Int( v ) и не содержит Int(parent( v )). То есть каждый узел в T хранит сегменты, охватывающие его интервал, но не охватывающие интервал его родительского узла. [3]
Строительство [ править ]
Дерево сегментов из множества сегментов I можно построить следующим образом. конечные точки интервалов в I. Сначала сортируются Отсюда получаются элементарные интервалы. Затем на элементарных интервалах строится сбалансированное двоичное дерево и для каждого узла v определяется интервал Int( v ), который он представляет. Осталось вычислить канонические подмножества узлов. Для этого интервалы I вставляются один за другим в дерево сегментов. Интервал X = [ x , x′ ] можно вставить в поддерево с корнем в T , используя следующую процедуру: [4]
- Если Int( T ) содержится в X , сохраните X в T и завершите.
- Еще:
- Если X пересекает интервал левого дочернего элемента T , затем рекурсивно вставьте X в этот дочерний элемент.
- Если X пересекает интервал правого дочернего элемента T , затем рекурсивно вставьте X в этот дочерний элемент.
Полная операция построения занимает время O ( n log n ), n — количество сегментов в 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 , запрос можно выполнить с использованием следующего алгоритма:
- Сообщите обо всех интервалах в I ( v ) .
- Если v не является листом:
- Если q x находится в Int (левый дочерний элемент v ), то
- Выполните запрос в левом дочернем элементе v .
- Если q x находится в Int (правый дочерний элемент v ), то
- Выполните запрос в правом дочернем элементе v .
- Если q x находится в Int (левый дочерний элемент v ), то
В дереве сегментов, содержащем n интервалов, те, которые содержат данную точку запроса, могут быть сообщены за время O (log n + k ), где k — количество сообщаемых интервалов.
Алгоритм запроса посещает один узел на каждом уровне дерева, то есть O (log n всего узлов ). С другой стороны, в узле v сегменты в I передаются за время O (1 + k v ), где k v — количество сообщаемых интервалов в узле v . Сумма всех k v для всех узлов v посещенных равна k , количеству сообщенных сегментов. [5]
Требования к хранению [ править ]
Дерево сегментов T на множестве I из n интервалов использует память O ( n log n ).
Лемма . Любой интервал [ x , x' ] из I хранится в каноническом наборе не более чем для двух узлов на одной и той же глубине.
Пусть v 1 , v 2 , v 3 — три узла на одной глубине, пронумерованные слева направо; и пусть p( v ) будет родительским узлом любого данного узла v . Предположим, [ x , x' ] хранится в v 1 и v 3 . Это означает, что [ x , x′ ] охватывает весь интервал от левой конечной точки Int( v 1 ) до правой конечной точки Int ( v 3 ). Обратите внимание, что все сегменты на конкретном уровне непересекаются и упорядочены слева направо: это справедливо по построению для уровня, содержащего листья, и свойство не теряется при переходе с любого уровня на уровень выше него путем объединения пар соседних сегментов. Теперь либо родитель( v 2 ) = родитель( 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 ). [5]
Обобщение для более высоких измерений [ править ]
Дерево сегментов можно обобщить на пространства более высокой размерности в виде многоуровневых деревьев сегментов. В версиях более высокой размерности дерево сегментов хранит набор параллельных осям (гипер) прямоугольников и может извлекать прямоугольники, содержащие заданную точку запроса. В структуре используется O ( n log д n ) хранилище и отвечает на запросы в O (log д п ) время.
Использование дробного каскадирования снижает время запроса, определяемое логарифмическим коэффициентом. Использование дерева интервалов на самом глубоком уровне связанных структур снижает ограничение памяти на логарифмический коэффициент. [6]
Примечания [ править ]
Запрос, который запрашивает все интервалы, содержащие данную точку, часто называют колющим запросом . [7]
Дерево сегментов менее эффективно, чем дерево интервалов, для запросов диапазона в одном измерении из-за более высоких требований к объему памяти: O ( n log n ) по сравнению с O( n ) дерева интервалов. Важность дерева сегментов заключается в том, что сегменты внутри канонического подмножества каждого узла могут храниться любым произвольным образом. [7]
Для n интервалов, конечные точки которых находятся в небольшом целочисленном диапазоне (например, в диапазоне [1,..., O ( n )]), оптимальные структуры данных [ который? ] существуют с линейным временем предварительной обработки и временем запроса O (1 + k ) для сообщения обо всех k интервалах, содержащих данную точку запроса.
Еще одним преимуществом дерева сегментов является то, что его можно легко адаптировать для подсчета запросов; то есть сообщать количество сегментов, содержащих данную точку, вместо того, чтобы сообщать сами сегменты. Вместо хранения интервалов в канонических подмножествах он может просто хранить их количество. Такое дерево сегментов использует линейное хранилище и требует времени запроса O (log n ), поэтому оно является оптимальным. [8]
Версии интервального дерева и дерева приоритетного поиска более высокой размерности не существуют; то есть не существует четкого расширения этих структур, решающего аналогичную проблему в более высоких измерениях. Но структуры можно использовать как связанные структуры деревьев сегментов. [6]
История [ править ]
![[икона]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( ноябрь 2007 г. ) |
Дерево сегментов было изобретено Джоном Бентли в 1977 году; в «Решениях задач о прямоугольнике Клее». [7]
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б ( из Berg et al. 2000 , стр. 227)
- ^ ( из Berg et al. 2000 , стр. 224)
- ^ ( из Berg et al. 2000 , стр. 225–226)
- ^ ( из Berg et al. 2000 , стр. 226–227)
- ↑ Перейти обратно: Перейти обратно: а б ( из Berg et al. 2000 , стр. 226)
- ↑ Перейти обратно: Перейти обратно: а б ( из Berg et al. 2000 , стр. 230)
- ↑ Перейти обратно: Перейти обратно: а б с ( из Berg et al. 2000 , стр. 229)
- ^ ( из Berg et al. 2000 , стр. 229–230)
Цитированные источники [ править ]
- де Берг, Марк; ван Кревелд, Марк; Овермарс, Марк; Шварцкопф, Отфрид (2000). «Больше геометрических структур данных». Вычислительная геометрия: алгоритмы и приложения (2-е изд.). Springer-Verlag Берлин Гейдельберг Нью-Йорк. дои : 10.1007/978-3-540-77974-2 . ISBN 3-540-65620-0 .
- http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf