c# - 调整二叉树的范围搜索以获得外部元素

Question

我有一个 RedBlack [Balanced, sorted] 二叉树，我正在搜索它以找到 [lower, upper] 范围内的所有值。

public IEnumerable<TData> Range(
      BinaryTree<TData> root, 
      IComparer<TData> comparer, 
      TData lower, 
      TData upper)
{
    var stack = new Stack<State>(16);
    BinaryTree<TData> here = root;

    do
    {
        if (here == null)
        {
            if (stack.Count == 0)
                break;

            State popped = stack.Pop();
            yield return popped.Data;
            here = popped.Next;
            continue;
        }

        if (comparer.Compare(here.Data, lower) < 0)
        {
            here = here.Right;
        }
        else if (comparer.Compare(here.Data, upper) > 0)
        {
            here = here.Left;
        }
        else
        {
            stack.Push(new State {Next = here.Right, Data = here.Data});
            here = here.Left;
        }
    } while (true);  
}

所以使用这段代码，如果我要用这些值构建一棵树

 [0, 1, 4, 5, 6, 9], 

并搜索范围内的所有元素

 [3, 8]

我会得到以下结果:

 [4, 5, 6]. 

我的问题是如何调整此算法以获得搜索的外部元素？像这样:

 [1, 4, 5, 6, 9]

即值 3 在树中位于 1 和 4 之间，所以我想返回 1，类似地，值 8 位于 6 和 9 之间，我希望结果中包含值 9。

一个问题是我不想从根目录重新开始搜索

目前使用 NGenerics 实现

[编辑]

愿意接受一般的算法答案。

Answer 1

我不确定您要用什么来填充红黑树。但是，如果您正在使用数组或数据流(其元素数量不会改变)，那么您可以使用 Segment Tree 来实现。

class SegmentTree
{
    class Node
    {
        int max, min, s, e;
        Node left, right;

        @Override
        public String toString()
        {
            String str = "Min: "+this.min+" Max: "+this.max+" "+this.s+"-"+this.e;
            return str;
        }
    }

    private Node root;

    public SegmentTree() {}

    public SegmentTree(int[] array)
    {
        add(array);
    }

    public void add(int[] array)
    {
        root = add(0, array.length-1, array);
    }

    private Node add(int s, int e, int[] array)
    {
        Node n = new Node();
        n.s = s;
        n.e = e;

        if(n.s==n.e)
        {
            n.min = n.max = array[n.s];
            return n;
        }

        int mid = s+(e-s)/2;
        n.left = add(s, mid, array);
        n.right = add(mid+1, e, array);
        n.max = Math.max(n.left.max, n.right.max);
        n.min = Math.min(n.left.min, n.right.min);

        return n;
    }


    // Get the max value between the limits l and r (both inclusive)
    public int getMax(int l, int r)
    {
        return getMax(root, l, r);
    }

    private int getMax(Node n, int l, int r)
    {
        if(l<=n.s && r>=n.e)
            return n.max;
        if(l>n.e || r<n.s)
            return Integer.MIN_VALUE;
        return Math.max(getMax(n.left, l, r), getMax(n.right, l, r));
    }   

    public int getMin(int l, int r)
    {
        return getMin(root, l, r);
    }

    private int getMin(Node n, int l, int r)
    {
        if(l<=n.s && r>=n.e)
            return n.min;
        if(l>n.e || r<n.s)
            return Integer.MAX_VALUE;
        return Math.min(getMin(n.left, l, r), getMin(n.right, l, r));
    }
}

注意

如果数据增加或减少，则必须重建树。如果有频繁的插入/删除/更新那么这根本不是一个好的选择。
当您有一组数据并且需要经常检查特定范围内的值时，这非常有用。
我给出了存储最小值和最大值的示例。您可以在 Node
中存储值的总和或任何其他内容为用 JAVA 编写代码表示歉意:)