Структура данных для хранения диапазонов

Question

мне интересно, если кто-нибудь знает, структуры данных, которые бы эффективно справиться со следующей ситуацией:

Структура данных должна хранить несколько, возможно, перекрывается переменной длины колеблется от некоторой непрерывной шкале времени.

• Например, вы можете добавить диапазоны a:[0,3], b:[4,7], c:[0,9].

• Время вставки не должно быть особенно эффективным.

извлечений бы диапазон в качестве параметра, и возвращает все диапазоны в наборе, которые перекрываются с диапазоном, например:

• Get(1,2) возвращают бы а и с. Get(6,7) вернет b и c. Get(2,6) вернет все три.

• Retrievals должны быть максимально эффективными.

Answer 1

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

Для поиска вы проверите свой диапазон ввода в левом и правом поддиапазонах верхнего узла и погрузитесь в те, которые перекрываются, повторяясь до тех пор, пока вы не достигнете фактических диапазонов, которые вы сохраните.

Таким образом, поиск имеет логарифмическую сложность. Вам все равно нужно управлять дубликатами при поиске, поскольку некоторые диапазоны будут принадлежать нескольким узлам.

Answer 2

Одной структурой данных, которую вы могли бы использовать, является одномерный R-tree. Они предназначены для работы с диапазонами и обеспечения эффективного поиска. Вы также узнаете о Allen's Operators; существует еще дюжина других отношений между временными интервалами, чем просто «перекрытия».

Есть другие вопросы на SO, которые посягают на этой области, в том числе:

• SO 325933
• SO 210729