範囲内の範囲内のノードの数0（LogN）内のバイナリ検索ツリー

Question

BSTと2つの整数aとb（a < b）が与えられた場合、どのようにしてノードの数を見つけることができますか？a <ノード値< b、O（log n）？

LogN時間でaとbの位置を簡単に見つけることができますが、通過を行わずにノードを数える方法はO（n）ですか？

Answer 1

に、また、その値よりも小さい（または、で言及異なるツリー設計のためにあるツリー内の値の数のカウントを維持下の脚注、左のサブツリーのノード）。

次に、値aを含むノードを見つけます。このノードに格納されているaより小さい値の数を取得します。このステップはLog（n）です。

ここで、値bを含むノードを見つけます。このノードに格納されているbより小さい値の数を取得します。このステップもLog（n）です。

2つのカウントを差し引くと、aとbの間のノードの数があります。この検索の合計複雑度は2 * Log（n）= O（Log（n））です。

---

_{this videoを参照してください。教授はここであなたの質問をSplay Treesを使って説明します。}

Answer 2

アイデアは簡単です。

1. ルートから始まるBSTをトラバースします。
2. すべてのノードが範囲内にあるかどうかをチェックします。 範囲内にある場合は++をカウントします。そして、両方の子供たちのために再発する。
3. 現在のノードが範囲の値より小さい場合は、右の子に対して再帰し、そうでない場合は左の子に対して再帰します。

時間の複雑さは、なぜそれがO(n)ではないことをあなたの質問のためにO(height + number of nodes in range) ...

になります。

ツリー内のノードの数であるツリー全体をトラバースしていないためです。親のデータに従って必要なサブツリーをたどるだけです。

擬似コード

int findCountInRange(Node root, int a, int b){ 

    if(root==null) 
     return 0; 
    if(root->data <= a && root->data >= b) 
     return 1 + findCountInRange(root->left, a, b)+findCountInRange(root->right, a, b); 
    else if(root->data < low) 
     return findCountInRange(root->right, a, b); 
    else 
     return findCountInRange(root->left, a, b); 

} 

Answer 3

ストアアレイ内のBSTのINORDERトラバーサル（それがソートされます）。 'a'と 'b'を検索すると、log（n）時間がかかり、そのインデックスが取得され、その違いが得られます。これは範囲 'a'のノードの番号を 'b'に与えます。

あなたのバイナリ検索ツリーの各ノードにはスペースの複雑さはO（n）