存储范围的数据结构

Question

我想知道是否有人知道有效处理以下情况的数据结构:

数据结构应该在某个连续的时间尺度上存储几个可能重叠的可变长度范围.

• 例如,您可以添加范围a:[0,3], b:[4,7], c:[0,9].

• 插入时间不需要特别有效.

检索将范围作为参数,并返回集合中与范围重叠的所有范围,例如:

• Get(1,2)将返回a和c. Get(6,7)将返回b和c. Get(2,6)将返回所有三个.

• 检索需要尽可能高效.

Answer 1

您可以使用的一种数据结构是一维R-tree。这些旨在处理范围并提供有效的检索。您还将了解Allen's Operators；除了“重叠”之外，时间间隔之间还有十几种其他关系。

关于 SO 的其他问题也影响到这一领域，包括：

• 确定两个日期范围是否重叠
• 单一维度内非重叠范围的数据结构

Answer 2

您可以选择二叉树，它将范围存储在层次结构中。从根节点开始，它表示一个包罗万象的范围，将其从中间划分，测试您尝试插入的范围是否属于左子范围、右子范围或两者，并在匹配的子节点中递归地进行，直到您尝试插入。达到一定深度，您可以在该深度保存实际范围。

对于查找，您可以根据顶部节点的左右子范围测试您的输入范围，并深入研究重叠的子范围，重复直到达到您保存的实际范围。

这样，检索就具有对数复杂度。您仍然需要在检索中管理重复项，因为某些范围将属于多个节点。