10

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

问题：

编写一个程序来跟踪一组文本范围。起点和终点将是字符串。

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

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

我们需要在这个范围内支持以下操作

  • 添加范围- 如果适用，这应该合并范围
  • 删除范围- 从跟踪范围中删除范围并重新计算范围
  • 查询范围- 给定一个字符，函数应该返回它是否是任何跟踪范围的一部分。

请注意，跟踪范围可以是不连续的。

我的解决方案：

我想出了两种方法。

  1. 将范围存储为双向链表或
  2. 将范围存储为某种平衡树，叶节点具有实际数据，并且它们以链表的形式相互连接。

您是否认为这个解决方案足够好，或者您可以想到任何更好的方法来做到这一点，以便这三个 API 为您提供最佳性能？

4

4 回答 4

10

您可能正在寻找区间树。

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

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

于 2012-10-04T06:32:53.070 回答
1

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

  • 删除先前插入的范围，并重新计算剩余范围的合并？

  • 停止跟踪已删除的范围，无论其部分已添加多少次。

这在算法上并没有太大的区别。这只是簿记。但重要的是要澄清。另外，范围是封闭的还是半开放的？（另一个不影响算法但影响实现的细节）。

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

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

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

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

合并和删除并不难，但有很多令人讨厌的情况。您首先找到与要插入/删除的范围的端点相对应的范围（使用标准查找操作），删除两者之间的所有范围，然后调整端点以纠正部分重叠的范围。虽然查找操作始终为 O(log n)，但树/向量操作为 o(n)（如果插入/删除的范围很大，无论如何）。

于 2012-10-04T05:20:21.240 回答
0

大多数语言，包括 Java 和 C++，都有某种有序映射或有序集合，您可以在其中查找一个值并找到一个值之后的下一个值或值之前的第一个值。您可以将其用作构建块 - 如果它包含一组不相交的范围，那么它将具有范围的最小元素，然后是范围的最大元素，然后是范围的最小元素，然后是范围的最大元素范围等。添加范围时，您可以检查是否保留了此属性。如果没有，您需要合并范围。同样，您希望在删除时保留它。然后，您可以通过查看查询点之前是否有最小元素和之后是否有最大元素来进行查询。

如果您想从头开始创建自己的数据结构，我会考虑某种 radix trie 结构，因为这样可以避免进行大量重复的字符串比较。

于 2012-10-04T05:35:46.797 回答
0

我认为您会选择 B+ 树，这与您提到的第二种方法相同。

以下是 B+ 树的一些性质：

  1. 所有数据都存储在叶节点中。
  2. 每片叶子都处于同一水平。
  3. 所有叶节点都有到其他叶节点的链接。

以下是一些应用程序 B+ 树：

  1. 它减少了在树中查找元素所需的 I/O 操作数。
  2. 常用于数据库索引的实现。
  3. B+ 树的主要价值在于在面向块的存储上下文中存储数据以进行有效检索 - 特别是文件系统。
  4. NTFS 使用 B+ 树进行目录索引。

基本上它有助于范围查询查找，最小化树遍历。

于 2016-08-01T03:08:21.993 回答