范围内的二叉搜索树过滤值

Question

我有一个由 N 个元素组成的树（RBT）。假设我有这棵树（N = 7）：

           4
    2             6
1       3      5     7

如何以比 O(N) 更好的性能过滤某个范围内的值（例如打印 3 到 6 之间的所有值）？

有没有具体的算法？我想象它类似于找到值 3 [log(N)] 的位置，以某种方式继续，直到到达 6 [O(M)]。

Answer 1

如果您有 Sedgevick 算法，第 4 版，请查看有关 BST 的第 3.2 章末尾。本书伴侣也有 Java 实现。

基本算法非常简单：对树进行递归中序遍历。将键放在队列（或任何容器）的左子树中，然后放在根的键，然后是右子树中的所有键。仅添加指定范围内的键，并跳过不能包含范围内键的子树的递归调用。

您可以在这里尝试- 这是一个基本的 BST（范围查询在 RBT 中的工作方式相同），其获取的值介于 3 和 6 之间。

算法本身：

public IEnumerable<T> Keys(T low, T high)
{
    var queue = new Queue<T>();
    Keys(Root, queue, low, high);
    return queue;
}

private void Keys(Node node, Queue<T> queue, T low, T high)
{
    if (node == null)
        return;

    int cmpLow = low.CompareTo(node.Key);
    int cmpHigh = high.CompareTo(node.Key);

    if (cmpLow < 0)
    {
        Keys(node.Left, queue, low, high);
    }
    if (cmpLow <= 0 && cmpHigh >= 0)
    {
        queue.Enqueue(node.Key);
    }    
    if (cmpHigh > 0)
    {
        Keys(node.Right, queue, low, high);
    }
}

复杂度应该是O(h + k)，其中h是树的高度，k是范围内的值的数量。还可以查看 擅长范围的范围树数据结构。