范围内的二进制搜索树过滤器值 [英] Binary search tree filter values in a range

问题描述

我有一个由N个元素组成的树(RBT).假设我有这棵树(N = 7):

I have a tree(RBT) consisting of N elements. Let's imagine I have this tree (N = 7):

           4
    2             6
1       3      5     7

如何过滤某些范围内的值(例如，打印3到6之间的所有值)，其性能要优于O(N)?

How do I filter values in some range (e.g. print all values between 3 and 6) with better performance than O(N)?

有没有特定的算法?我在想像是找到值为3 [log(N)]的位置，以某种方式继续下去，直到达到6 [O(M)].

Is there any specific algorithm? I'm imagining it something like find position of value 3 [log(N)], somehow continue until you get to the 6 [O(M)].

推荐答案

如果您有Sedgevick的算法，第4版，请参阅第3.2章有关BST的结尾.另外，同伴具有Java实现.

If you have Sedgevick's Algorithms, 4 ed., look at the end of chapter 3.2 on BST's. Also book companion has implementation in Java.

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

Basic algorithm is very simple: do recursive inorder traversal of the tree. Put keys in the left subtree in the queue (or whatever container), then key at root, then all keys in the right subtree. Add only keys that are in specified range, and skip recursive calls for subtrees that cannot contain keys in range.

您可以在此处试试-这是一个基本的BST(范围查询在RBT中的工作原理相同)得到3到6之间的值.

You can try this here - this is a basic BST (range queries work the same in RBT) with getting values between 3 and 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 是范围内的值数.还可以查看擅长范围的范围树数据结构.

Complexity should be O(h + k), where h is height of the tree and k is number of values in range. Also have a look at Range Tree datastructre that is good at ranges.

这篇关于范围内的二进制搜索树过滤器值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！