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

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

           4
    2             6
1       3      5     7

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

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

如果您有 Sedgevick 算法，第 4 版，请查看第 3.2 章末尾有关 BST 的内容。还预订伴侣 https://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html有Java实现。

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

你可以试试这个here https://dotnetfiddle.net/pzR4sY- 这是一个基本的 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), where h是树的高度，k是范围内的值的数量。 还可以看看范围树 https://en.wikipedia.org/wiki/Range_tree擅长范围的数据结构。