存储区间的数据结构

Question

我想知道是否有一种数据结构能有效地处理以下情况:

该数据结构应存储一些可能重叠的可变长度范围，这些范围在某个连续时间尺度上。

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

• 插入时间不需要特别高效。

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

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

• 检索需要尽可能高效。

- Kevin

Answer 1

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

还有其他与此领域相关的SO问题，包括：

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

- Jonathan Leffler

Answer 2

你可以使用二叉树来存储层次结构中的范围。从代表包含所有范围的根节点开始，将其分为两半，测试您要插入的范围是属于左侧子范围、右侧子范围还是两者都是，并在匹配子节点中递归继续，直到达到某个深度，此时保存实际范围。

对于查找，您可以将输入范围与顶部节点的左侧和右侧子范围进行比较，并潜入重叠的范围中，重复此过程，直到到达要保存的实际范围。

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

- small_duck