Лучшая структура данных, позволяющая эффективно использовать все диапазоны (min, max), такие что значение> = min и значение <= max?

Question

Представьте, что у меня есть набор минимальных и максимальных значений. Мне нужна структура данных, которая, учитывая внешнее значение, будет наиболее эффективно давать мне пары (min, max), для которых значение> = min, значение <= max. </p>

Если вы знаете, что диапазоны не перекрываются, я думаю, вы могли бы просто выполнить сбалансированное бинарное дерево поиска по min, и первый узел с удовлетворяющим (min, max) должен быть единственным. Но если диапазоны могут перекрываться, есть ли структура данных, которая позволит вам сделать это эффективно?

Answer 1

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

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

Answer 2

Я думаю, что ответ на самом деле может быть следующим: http://en.wikipedia.org/wiki/Interval_tree. Учитывая точку или набор точек, она позволяет эффективно тянуть удовлетворительные интервалы. Единственное предостережение, конечно, в том, что построение исходной структуры данных неэффективно, но это также неизбежно при любом индексировании и т. Д.

Answer 3

Запрос может быть решен с помощью Range Tree : двоичного дерева двоичных деревьев .

Внешнее дерево - это дерево поиска по значениям x пар (x, y). Пары (x, y) хранятся в листовых узлах. Каждый узел V внешнего дерева содержит указатель на y-индексированное дерево поиска Y, содержащее все пары поддерева V.

Чтобы решить запрос диапазона ([Значение, бесконечность) = RangeX, RangeY), найдите во внешнем дереве поиска крайний левый x _min , удовлетворяющий Value <= x <sub>min . Пусть V будет узлом на пути к x _min . Если поиск идет влево, тогда дерево поиска Y поддерева V right содержит пары, которые находятся в RangeX. Добавьте все пары Y, которые находятся в RangeY к результату.

Answer 4

Один из возможных подходов состоит в том, чтобы поместить (min, max) в массив и отсортировать по виду. Затем используйте бинарный поиск, чтобы найти область в массиве, где min соответствуют критериям, а затем выполните поиск.