目前我正在为我的大学项目用 Java 实现 BST。正如我们所知，BST 在平衡树中搜索复杂度为 O(log n) 的 单个 单元时非常好。
但是如何在值a和b之间进行查找呢？ (a < b)
假设我有这棵树
│ ┌── 125
│ ┌── 122
│ │ └── 120
│ ┌── 117
│ │ │ ┌── 113
│ │ └── 112
│ │ └── 108
│ ┌── 86
│ │ │ ┌── 85
│ │ └── 72
└── 59
│ ┌── 56
│ ┌── 52
│ ┌── 47
│ │ │ ┌── 43
│ │ └── 39
│ │ │ ┌── 38
│ │ └── 36
└── 28
│ ┌── 18
│ ┌── 15
└── 2
└── 1
我想创建一个方法 range(a,b) 以返回 a 和 b 之间的值(包括在内)。 (注意:a 和 b 在树中不是必需的!)
例如:range(53,112) 将返回 56,59,72,85,86,108,112
这是我的伪代码
/* recursive method */
range(a,b)
range(a,b,root);
/* helper method */
range(a,b,node)
if (a <= node.value <= b)
if (node.left != null) and (node.value != a)
range(a,b,node.left)
print node.value
if (node.right != null) and (node.value != b)
range(a,b,node.right)
else if node.value < a
if (node.right != null)
range(a,b,node.right)
else // node.value > b
if (node.left != null)
range(a,b,node.left)
但是我觉得我的方法比较慢。
例如，在一个排序数组中，我们要对a和b进行二分查找，得到它们各自的索引。之后，我们从 a 的索引迭代到 b 的索引。
BST 在搜索多个值时确实会执行得更慢吗？是否可以改进我的算法使其与排序数组一样快？
最佳答案
根据返回结果的方式，排序数组可能具有无需在任何地方复制结果的巨大优势。与将范围的另一个副本放入另一个缓冲区相比，仅将指针+长度 View 返回到数组中要快得多并且对缓存更友好。一棵树总是必须从树中复制元素。即使您确实需要副本(修改或其他)，memcpy 也比走树快得多。
如果您可以在遍历树的同时进行处理(就像您使用 print 所做的那样)，这就不是问题。
我似乎总是在谷歌搜索之前写下答案。结果是 trees to answer range queries are a thing .显然，它通常用于 2D 或 3D 范围(例如，每个点都有 x 和 y 坐标)，而排序数组无法做到这一点。我认为这是因为即使它尽可能高效，它也没有将指针+长度窗口返回到排序数组中那么高效!
我不会从维基百科复制/粘贴整个算法，只是聪明的想法:
To report the points that lie in the interval [x1, x2], we start by searching for x1 and x2. At some vertex in the tree, the search paths to x1 and x2 will diverge
这就是您如何有效地检测您知道将在您的范围内的整个子树的方法，有关详细信息，请参阅维基百科和/或谷歌“树范围查询”。
我在谷歌搜索前的观察是，您可以避免比较，而只需遍历一些子树。在您的示例中，保证 86 的左子树都在范围内，因为我们知道它们都是 >59 和 <86，这比 [a. .b]。我没有想到一种方法来寻找这种特殊情况，这种情况可能不会比节省的开销更多。
关于algorithm - 获取二叉搜索树的间隔与排序数组一样快，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32303154/