範囲内のバイナリ検索ツリーフィルタ値

Question

私はN個の要素からなるツリー（RBT）を持っています。

  4 
    2    6 
1  3  5  7 

どのように私はO（N）よりも高いパフォーマンスを（例えば3と6の間のすべての値を印刷する）、いくつかの範囲内の値をフィルタします：のは、私はこの木を持っている（N = 7）想像してみましょうか？

特定のアルゴリズムはありますか？私は値3の位置を見つけるような何かを想像しています[log（N）]、あなたは6 [O（M）]に達するまで何とか続けます。

Answer 1

Sedgevick's Algorithms（4版）をお持ちの場合は、BSTの3.2章の最後を見てください。また、書籍companionにはJavaで実装されています。

基本的なアルゴリズムは非常に簡単です：ツリーのinorder traversalを再帰的に実行します。キュー内の左のサブツリーにキーを入れてから、ルートのキーを押してから、右のサブツリーのすべてのキーを押します。指定した範囲内のキーのみを追加し、範囲内のキーを含むことのできないサブツリーの再帰呼び出しをスキップします。

あなたはこのhereを試すことができます - これは基本的なBSTです（範囲クエリは、RBTで同じように機能する）3と6

アルゴリズム自体の間の値を取得して：複雑さはO(h + k)あるべき

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); 
    } 
} 

ここで、はツリーの高さであり、kは範囲内の値の数です。 また、Range Tree datastructreの範囲を調べてみてください。