1. 序章


このチュートリアルでは、二分探索木（BST）でノードの順序どおりの後続を見つける3つの方法を示します。 このようなツリーでは、各ノードは、左側のサブツリーのノードであり、右側のサブツリーのノードではありません。








ノードは、数値、文字列、タプル、一般に、相互に比較できるオブジェクトにすることができます。


2. ノードのインオーダーサクセサとは何ですか？


インオーダートラバーサルは、次のように再帰的に定義するツリートラバーサル手法です。




BSTに適用すると、次のツリーの例のように、降順ではない順序でノードにアクセスします。


私たちの目標は、ツリーの順序通りのトラバースで特定のノードのすぐ後継者を見つけることです。 後続ノードは、ツリー内よりも大きいすべてのノードの中で最小のノードです。


2.1. 注文後継者はどこにありますか？


上の画像を見ると、パターンが見えます。


ノードに右の子がある場合、その後続ノードはその右のサブツリーの最小ノードです。つまり、この場合、ノードの後続ノードはその右の子の左端の子孫です。 なんで？ なぜなら、訪問した後、トラバーサル手順はの右のサブツリーを処理し、最初に訪問したのはその左端の葉であるためです。


右の子がない場合、その順序の後続関数は、ツリー内でその祖先の中でその上に配置されます。再帰呼び出しを展開している間、順序のトラバーサル関数は最初に、左の子があったノードにアクセスします。最新の入力。 したがって、’後継者は、左の子である’最年少の祖先の親です。


3. アウトツリーで後継者を見つける


通常、ノードは3つの属性を持つ構造として実装されます。 1つはノードのコンテンツです。ツリー階層のその場所に配置されたオブジェクトです。 他の2つは、ノードの左と右の子へのポインターです。 概念的には、この実装はアウトツリーに対応します。つまり、ルートから離れた方向にエッジが向けられたツリーです。


3.1. アルゴリズム


アウトツリーでノードの順序どおりの後続ノードを見つけるには、最初にノードを見つけて、途中で左の子の親を記憶する必要があります。 それを見つけたら、適切な子がいるかどうかを確認します。 その場合は、右のサブツリーの左端の葉を返します。 それ以外の場合は、ノードの上に最後に記憶された親を返します。




が最大ノードの場合、後続ノードはありません。 したがって、その場合は、を返します。


3.2. 複雑さの分析


BST全体の高さとします。 ツリー内のからへのパスの長さとします。 適切な子がない場合は、ノードにアクセスしてを検索します。 その後、それ以上の処理をせずにサクセサを出力します。 適切な子がいる場合は、葉に到達すると後継者を見つけます。 木の葉の深さは、木の高さによって上から制限されます。 したがって、最悪の場合、ステップ以上のことはしません：


ツリーのバランスが取れている場合、それはそれを保持するため、アルゴリズムは対数時間で実行されます。ここで、はツリー内のノードの数です。 ただし、バランスの取れていないツリーは縮退している可能性があります。 それらの高さは最悪の場合であるため、アルゴリズムはそのような入力に対して線形になります。


4. BSTの双方向実装で後継者を見つける


通常、ノードには子へのポインタのみが含まれます。 ただし、親へのポインタも保存することがあります。 その理由は、多くのツリー操作を簡素化するためです。 この方法でより多くのメモリを使用しますが、ほとんどの場合、オーバーヘッドはごくわずかです。


4.1. アルゴリズム


このようなツリーでは、を検索するときに、左の子を持つ最新の親を追跡する必要はありません。 代わりに、存在しない場合は、探しているポインターが見つかるまで、親へのポインターに従います。




このアプローチの複雑さは、アウトツリーのアルゴリズムの複雑さと同じです。


5. 注文検索


3番目の最後の方法は、順序どおりの検索です。 のすぐ後継者を探しているので、より大きいノードにアクセスするまで、順序どおりのトラバーサルを実行できます。 順序どおりの手順では、降順ではない順序でノードにアクセスするため、最初にアクセスしたノードが後続ノードよりも大きいことを確認できます。


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




5.1. 複雑さの分析


このメソッドはノードをトラバースします。ここで、はツリー内のノード間のランクです。


最悪の場合、が最大のノードになるので、。 したがって、順序どおりの検索はすべてのノードにアクセスし、最悪のシナリオで時間内に実行されます。


6. 討論


どのアルゴリズムを選択しますか？ 最初の2つはノードのランクの影響を受けませんが、3番目のアプローチの複雑さはツリーの高さに依存しません。


一見すると、最初の2つのアルゴリズムの方が優れているように見えるかもしれません。 結局のところ、ツリーのバランスが取れている場合、両方とも対数時間計算量になりますが、順序どおりのアプローチはいずれの場合も線形です。 ただし、バランスの取れたツリーを構築して維持することは簡単な作業ではありません。 たとえば、ツリーを頻繁に更新するが、ほとんどの場合、下位ノードの後続ノードを要求する場合、実際には、順序どおりの検索がより高速に実行されます。 その理由は、更新ではツリーのバランスを取り直す必要がないためです。


重複エントリはどうですか？最初の2つのアルゴリズムは、を含むルートノードに最も近いものを見つけます。 これに等しい他のすべてのノードは左側のサブツリーにあり、これはまったく処理されません。 したがって、返される後継者は、最初の大なり記号になります。 これは、3番目のアプローチにも当てはまります。


7. 結論


この記事では、ノードのインオーダーサクセサを見つける3つの方法を紹介しました。 1つは、インオーダートラバーサルアルゴリズムの単純な拡張です。 ファクトのもう1つの使用法は、ノードの後継が右の子の左端の子孫であるか、左の子である最年少の祖先の親であるということです。