1. 序章


このチュートリアルでは、二分探索木で-番目に小さい要素を見つける方法を示します。


2. -番目に小さい要素








二分探索木に次の要素があると仮定します。 -番目に小さいものを見つけたい。 正式には、がのソートされた順列である場合、指定された。に対して検索します。


このツリーを例として取り上げましょう。


各ノードの値は右の子孫の値よりも低く、左のサブツリーの値以上であるため、これは二分探索木です。 たとえば、。 ツリーで5番目に小さい数字は次のとおりです。


3. 順序通りのトラバーサルで-番目に小さい要素を見つける


ツリーのin-ordertraversal はその要素をソートされた順序で出力するため、要素を取得するまでトラバーサルを実行できます。 その時点で、必要な要素が得られたので停止できます。




トラバーサル手順をイテレータとして使用したため、キーワード利回りを使用しました。 もちろん、完全に再帰的なアルゴリズムも機能します。


3.1. 複雑


このアプローチはすべての二分探索木で機能しますが、線形時間計算量です。 の場合、アルゴリズムはツリー全体をトラバースして最大の要素に到達します。


4. サブツリーを飛び越えて、-番目に小さい要素を見つける


各ノードにその子孫の数を格納すると、-番目に小さい要素をより効率的に見つけることができます。 例えば：


追加情報により、（順番に）トラバースを高速化できます。 の前にノードにアクセスし、の左側のサブツリーにノードがある場合、。の場合はトラバースをスキップできます。 なんで？ これは、-番目に小さい要素がサブツリーにないことを確認できるためです。 したがって、それを「ジャンプ」するのは安全です。 そうすることで、2つのケースを区別します。 の場合、はツリー内で-番目に小さい要素です。 の場合、スキップして右側のサブツリーに直接移動できます。


逆に、の場合、-番目に小さい要素は確かに左側のサブツリーにあります。


4.1. 擬似コード


擬似コードは次のとおりです。




最初に、要素が存在するかどうかを確認するかどうかをテストできます。


4.2. 例


変更されたトラバーサルの効率を示すために、5番目に小さい要素を見つける前に、上記のツリーでアクセスするノードの数を確認しましょう。


対照的に、通常の順序どおりの検索では、ジャンプした左側のサブツリー内のすべてのノードにアクセスします。


4.3. 複雑


最悪の場合、ジャンプするサブツリーは可能な限り最小です。 この状況は、ツリー内の各ノードに適切な子しかない場合に発生します。 このようなツリーは、本質的にリンクリストです。 各ステップでゼロノードを飛び越え、合計でトラバースします。


一般に、子をジャンプする各ノードは、ルートからシークされた値を含むノードへのパス上にあります。 したがって、このアルゴリズムの最悪の場合の時間計算量はです。ここで、はツリーの高さ、つまりルートからリーフまでの最長パスです。 ツリーがバランスである場合、アルゴリズムは対数の複雑さを持ちます。サブツリーのサイズに関する追加情報がなければ、通常のトラバーサルは、ツリーはバランスが取れていました。


ただし、ツリーのバランスをとると計算のオーバーヘッドが増えるため、このアプローチは、ルックアップが挿入や削除よりも頻繁に行われる場合にのみ効果があります。このアルゴリズムの理想的なユースケースは、一度作成した検索ツリーです。後で変更します。


5. 結論


この記事では、二分探索木で-番目に小さい要素を見つける方法を示しました。 通常の順序どおりのトラバーサルを使用できますが、複雑です。 各サブツリーのサイズをルートに保持すると、バランスの取れたツリーを使用する場合に、より効率的なアプローチが可能になります。