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

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 版，请查看第 3.2 章末尾关于 BST 的内容。另订companion有 Java 实现。

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

你可以试试这个here - 这是一个基本的 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 是范围内值的数量。 也看看 Range Tree擅长范围的数据结构。