范围查询的数据结构

Question

我最近被问到关于以下问题的编码问题.我有一些解决这个问题的方法,但我不确定这些问题是否最有效.

问题:

编写程序来跟踪文本范围集.起点和终点将是字符串.

Text range example : [AbA-Ef]
 Aa would fall before this range
 AB would fall inside this range
 etc.

字符串比较就像'A'<'a'<'B'<'b'...'Z'<'z'

我们需要支持此范围内的以下操作

请注意,跟踪范围可以是不连续的.

我的解决方案

我提出了两种方法.

您认为这个解决方案是否足够好,或者您可以考虑采用更好的方法来实现这三个API,从而提供最佳性能？

Answer 1

您可能正在寻找间隔树.

将数据结构与自定义比较器一起使用以指示"范围内的内容",您将能够有效地执行所需的操作.

注意,间隔树实际上是实现第二个想法的有效方式(Store ranges as a some sort of balanced tree)

Answer 2

我不清楚“删除范围”操作应该做什么。可以;

这在算法上并没有产生巨大的差异；这只是簿记。但澄清这一点很重要。另外，范围是封闭的还是半开放的？（另一个细节不影响算法，但会影响实现）。

解决这个问题的基本方法是将跟踪集合并到不相交（不重叠）范围的排序列表中；作为向量或二叉搜索树，或者基本上任何支持 O(log n) 搜索的结构。

一种方法是将每个不相交范围的两个端点放入数据结构中。要查明目标值是否在某个范围内，请查找大于目标的最小端点的索引。如果索引是奇数，则目标在某个范围内；甚至意味着它在外面。

或者，通过起始点对所有不相交的范围进行索引；通过搜索不大于目标的最大起点来找到目标，然后将目标与相关终点进行比较。

我通常对排序向量使用第一种方法，如果 (a) 空间利用率很重要并且 (b) 插入和合并相对较少，则这种方法是合理的。对于二叉搜索树，我采用第二种方法。但它们仅在细节和常数上有所不同。

合并和删除并不困难，但是有大量令人烦恼的情况。首先查找与要插入/删除的范围的端点相对应的范围（使用标准查找操作），删除两者之间的所有范围，然后摆弄端点以纠正部分重叠的范围。虽然查找操作始终为 O(log n)，但树/向量操作为 O(n)（如果插入/删除范围很大的话）。