用于表示和查询未来时间间隔的数据结构

Question

我想表示未来系统中某个元素的预测状态。元素可以处于状态S1或S2。 S1预测是<t_start, t_end>形式的非重叠区间，其中t_是未来的相对时间。间隔的缺失意味着状态是S2并且只有S1预测。主要的操作是添加预测的时间间隔和查询任意未来时间的状态。状态查询将比查询更频繁地发生几个数量级。可以在有限范围内的任何时间添加间隔，相对于现有时间间隔，可以以任何顺序添加。另一个重要的操作是时间的进步，这意味着预测越来越接近并最终进入过去，在那里他们可以被遗忘。预测可能很少被删除，但这不是必需的。时间的基本模型可以是连续的，也可以离散为整数时间步长。

我已经有一个使用链接列表的实现，其中列表中的位置表示时间（使用分散到整数的时间）并且节点内容是S1或S2。这随着时间的推移而更新（您只需放弃第一个节点），并且查询速度相当快（未来时间步数的线性）。但是，由于您列举了所有可能的时间片，所以在添加预测方面它有点难看，并且随着您增加时间范围或时间片的精度而缩小。因此，我正在寻找一种替代方法（例如基于间隔以某种方式）。

Answer 1

一种可能性是将间隔存储在二叉搜索树中。如果您可以忍受其线性时间最坏的情况行为，我会建议您使用splay tree，因为它会自行调整以处理摊销后的恒定时间内有利的查询模式。

由于间隔不重叠，搜索BST非常简单。如果查询点包含在当前时间间隔中，那么我们就完成了。如果它位于左侧，则搜索左侧子树。如果它位于右侧，则搜索右侧子树。