Войти
В информатике, дерево сегментов, также известное как дерево статистики, представляет собой дерево структуру данных, используемую для хранения информации о интервалах или сегментах. Он позволяет запросить, какой из сохраненных сегментов содержит данную точку. В принципе, это статическая структура; то есть это структура, которую нельзя изменить после постройки. Подобной структурой данных является дерево интервалов.
Сегментное дерево для набора I из n интервалов использует O (n log n) хранилище и может быть построено за O (n log n) время.. Деревья сегментов поддерживают поиск всех интервалов, содержащих точку запроса в O (log n + k), где k - количество извлеченных интервалов или сегментов.
Приложения дерева сегментов находятся в областях вычислительная геометрия и географические информационные системы.
Сегментное дерево может быть обобщено на пространства более высокого измерения.
В этом разделе описывается структура дерева сегментов в одномерном пространстве.
Пусть S будет набором интервалов или сегментов. Пусть p 1, p 2,..., p m будет списком отдельных конечных точек интервала, отсортированных слева направо. Рассмотрим разбиение вещественной прямой, вызванное этими точками. Области этого разбиения называются элементарными интервалами. Таким образом, элементарные интервалы слева направо:
![{\ 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)
То есть список элементарных интервалов состоит из открытых интервалов между двумя последовательными конечными точками p i и p i + 1, чередующихся с закрытые интервалы, состоящие из одной конечной точки. Отдельные точки рассматриваются как интервалы, потому что ответ на запрос не обязательно будет одинаковым внутри элементарного интервала и его конечных точек.
Графический пример структуры дерева сегментов. Этот экземпляр построен для сегментов, показанных внизу. Учитывая набор I интервалов или сегментов, дерево сегментов T для I структурировано следующим образом:
В этом разделе анализируется стоимость хранения дерева сегментов в одномерное пространство.
Сегментное дерево 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). Обратите внимание, что все сегменты на определенном уровне не перекрываются и упорядочены слева направо: это верно по конструкции для уровня, содержащего листья, и свойство не теряется при переходе с любого уровня на уровень выше, путем объединения пар смежных сегментов. Теперь либо 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 можно построить следующим образом. Сначала сортируются конечные точки интервалов в I. Из этого получаются элементарные интервалы. Затем на элементарных интервалах строится сбалансированное двоичное дерево, и для каждого узла v определяется интервал Int (v), который он представляет. Осталось вычислить канонические подмножества узлов. Для этого интервалы в I вставляются один за другим в дерево сегментов. Интервал X = [x, x ′] может быть вставлен в поддерево с корнем в T, используя следующую процедуру:
Полная операция построения занимает O (n log n) времени, n - количество сегментов в I.
Доказательство —Посещение каждого узла занимает постоянное время (при условии, что канонические подмножества хранятся в простой структуре данных, такой как связанный список ). Когда мы посещаем узел v, мы либо сохраняем X в v, либо Int (v) содержит конечную точку X. Как доказано выше, интервал сохраняется не более двух раз на каждом уровне дерева. Также существует не более одного узла на каждом уровне, чей соответствующий интервал содержит x, и один узел, интервал которого содержит x '. Таким образом, посещается не более четырех узлов на каждом уровне. Поскольку существует O (log n) уровней, общая стоимость вставки равна O (log n).
В этом разделе описывается операция запроса дерева сегментов в одномерном пространстве.
Запрос дерева сегментов, получает точку q x (должен быть одним из листьев дерева) и извлекает список всех сохраненных сегментов, которые содержат точку q x.
Официально заявлено; учитывая узел (поддерево) v и точку запроса q x, запрос может быть выполнен с использованием следующего алгоритма:
В дереве сегментов, которое содержит n интервалов, те, которые содержат о заданной точке запроса можно сообщить за время O (log n + k), где k - количество отчетных интервалов.
Доказательство -Алгоритм запроса посещает один узел на каждом уровне дерева, так что всего O (log n) узлов. С другой стороны, в узле v сегменты в I сообщаются за время O (1 + k v), где k v - количество интервалов в узле v, сообщил. Сумма всех k v для всех посещенных узлов v равна k, числу сегментов, о которых сообщается.
Дерево сегментов может быть обобщено для более высоких измерений пространства в виде многоуровневых сегментных деревьев. В версиях с более высокой размерностью сегментное дерево хранит коллекцию параллельных осям (гипер-) прямоугольников и может извлекать прямоугольники, содержащие заданную точку запроса. Структура использует хранилище O (n log n) и отвечает на запросы за O (log n).
Использование дробного каскадирования снижает время запроса, ограниченное логарифмическим коэффициентом. Использование дерева интервалов на самом глубоком уровне связанных структур снижает ограничение памяти на логарифмический коэффициент.
Запрос, который запрашивает все интервалы, содержащие данную точку часто называют острым запросом.
Дерево сегментов менее эффективно, чем дерево интервалов для запросов диапазона в одном измерении, из-за более высоких требований к памяти: O (n log n) против O (n) интервального дерева. Важность дерева сегментов состоит в том, что сегменты внутри канонического подмножества каждого узла могут быть сохранены любым произвольным образом.
Для n интервалов, конечные точки которых находятся в диапазоне малых целых чисел (например, в диапазоне [1,…, O (n)]) существуют оптимальные структуры данных с линейным временем предварительной обработки и временем запроса O (1 + k) для сообщения всех k интервалов, содержащих заданную точку запроса.
Еще одно преимущество дерева сегментов состоит в том, что его можно легко адаптировать для подсчета запросов; то есть, чтобы сообщить количество сегментов, содержащих данную точку, вместо того, чтобы сообщать сами сегменты. Вместо того, чтобы хранить интервалы в канонических подмножествах, он может просто хранить их количество. Такое дерево сегментов использует линейное хранилище и требует времени запроса O (log n), поэтому оно является оптимальным.
Версии дерева интервалов с более высокой размерностью и приоритетное дерево поиска не работают. существовать; то есть не существует четкого расширения этих структур, которое решает аналогичную проблему в более высоких измерениях. Но эти структуры можно использовать как связанную структуру деревьев сегментов.
Дерево сегментов было изобретено Джоном Луи Бентли в 1977 году; в «Решениях проблем прямоугольника Кли».
