二叉搜索树的间隔与排序数组一样快

Question

目前我正在为我的大学项目实施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在搜索多个值时执行速度是否正常？是否有可能将我的算法提高到与排序数组一样快？

Answer 1

根据返回结果的方式，排序数组可能具有不需要将结果复制到任何地方的巨大优势。与将范围的另一个副本放入另一个缓冲区相比，仅将指针+长度视图返回到数组要快得多且对缓存更友好。树总是必须从树中复制元素。即使您确实需要一个副本（用于修改或其他），memcpy 也比遍历树快得多。

如果您可以在遍历树时进行动态处理（就像您使用 所做的那样print），那么这不是问题。

我似乎总是在谷歌搜索之前写下答案。事实证明，用树来回答范围查询是一回事。显然，它通常是针对 2D 或 3D 范围（例如，每个点都有 x 和 y 坐标）完成的，而使用排序数组无法做到这一点。我认为这是因为尽管它尽可能高效，但它不如将指针+长度窗口返回到排序数组那么高效！

我不会从维基百科复制/粘贴整个算法，只是一个聪明的想法：

为了报告位于区间 [x1, x2] 中的点，我们首先搜索 x1 和 x2。在树中的某个顶点，x1 和 x2 的搜索路径将发散

这就是您如何有效地检测您知道将在您的范围内的整个子树的方法，请参阅维基百科和/或谷歌“树范围查询”以获取更多详细信息。

我在谷歌搜索之前的观察是，您可以避免比较，而只需遍历一些子树。在您的示例中， 的 左子树86保证全部在该范围内，因为我们知道它们都 >59 且 <86，这是比 更紧密的界限[a..b]。我没有想到一种方法来寻找这种特殊情况，而这种特殊情况所花费的开销可能不会超过所节省的开销。