二分探索木のノードのランク
1. 序章
このチュートリアルでは、二分探索木(BST)内のノードのランクを決定する3つの方法を紹介します。
2. ツリー内のノードのランク
ツリー内のノード値のランクは、値がであるノードの数です。ノードは、順序関係が付いている限り、任意のデータ型にすることができます。 たとえば、次のツリーののランクは次のとおりです。
したがって、ツリーの値とルートがあり、目標はその中ののランクを見つけることです。
それがツリーに存在するとは想定していません。 そうである場合、それは繰り返されるかもしれません。 ここで紹介するアプローチは、すべてのケースをカバーしています。
3. ランクを決定するためのブルートフォース法
最も明白なアプローチは、ノードの数を再帰的に計算して、左右のサブツリーの値で合計することです。 ルートが、の場合、合計を。だけインクリメントします。 そうでない場合、合計はツリー全体のランクです。
3.1. 擬似コード
擬似コードは次のとおりです。
3.2. 例
このブルートフォースメソッドが次のツリーでのランクを計算する方法を見てみましょう。
それは葉までずっと行き、ルートに到達するまでサブツリー内のランクを再帰的に伝播します。
3.3. 複雑
このアプローチは効率的ではありません。 私たちは常にツリー全体をトラバースするので、時間複雑性は、ノードの数です。 その理由は、ツリーが順序付けられているという事実を使用しないためです。
4. ランクの順序ベースの計算
右側のサブツリーのすべてのノードも。より大きいため、計算する必要はありません。 したがって、2つのケースを区別します。
- の場合、左と右の両方のサブツリーで再帰呼び出しを行う必要があります。
- の場合、正しいサブツリーを無視できます。
擬似コードは次のとおりです。
4.1. 例
これは、順序ベースの方法が次のランクを決定する方法です。
ご覧のとおり、訪問されたのは以下のノードのみです。
4.2. 複雑
最悪のシナリオは、がツリー内のすべてのノードよりも大きい場合に発生します。 アルゴリズムはツリー全体をトラバースすることになります。したがって、最悪の場合の時間計算量は、ブルートフォースアプローチの場合と同じです。
それでも、このメソッドはブルートフォースよりも高速に実行されます。これは、任意のノードを正確に訪問するのに対し、ブルートフォースソリューションはランクに関係なくノードを訪問するためです。
ただし、少し簿記をする準備ができていれば、さらにスピードアップできます。
5. ランク計算のための順序統計量ツリー
各ノードにそのサイズに関する情報を追加すると、左側のサブツリーのトラバースをスキップできます。 代わりに、size属性の値を読み取り、右側のサブツリーでのみ再帰します。
ノードにサイズが格納されているツリーは、値のランクに関するクエリに効率的に回答し、指定されたランクを持つノードを見つけることができます。 このようなツリーは、順序統計ツリーと呼ばれます。
5.1. 例
このアルゴリズムがどのノードにアクセスしてランクを決定するかを見てみましょう。
ルートはであるため、左側のサブツリー()のサイズを読み取り、にを追加してルートをカウントし、右側のサブツリーで繰り返します。 右のサブツリー()のルートは、右の子孫と一緒に無視できるようにするためのものです。 したがって、左の子に対して再帰的な呼び出しを行います。 それもなので、また左に行きます。 ただし、子は残っていないので、ツリー全体のルートに戻って伝播します。 このようにして、ランクをとして計算します。これは正しい結果です。
5.2. 複雑
このメソッドは、ツリー内の単一のパスをトラバースして、入力値のランクを見つけます。
ツリーのバランスが取れている場合、ツリーはそれを保持するため、最悪の場合、アルゴリズム全体が対数的に複雑になります。 ただし、ツリーのバランスを保つには、更新のたびにツリーのバランスを取り直す必要があります。
ツリーのバランスが崩れている場合、最悪のケースは、すべてのノードよりも大きい単一のブランチで構成される縮退ツリーです。 その場合、アルゴリズムはすべてのノードにアクセスし、他の2つのアプローチと同じように最悪の場合の複雑さを持ちます。
5.3. 末尾再帰ランクの計算
前の2つの方法とは異なり、この方法は末尾再帰にすることができます。これは、再帰呼び出しの戻り値には、呼び出しスタックを渡す以外に何もないためです。 関数を末尾再帰形式に変換するために、部分的な結果を累積し、returnステートメントが関数の本体で最後に実行されるステートメントであることを確認します。
末尾再帰関数は末尾呼び出しを最適化できます。つまり、呼び出しスタック上の1つのフレームを呼び出しごとに再利用できます。 末尾呼び出しの最適化がないと、アクセスするパスが深すぎる場合にスタックオーバーフローエラーが発生するリスクがあります。
さらに、末尾再帰関数を反復関数に変換する簡単な方法があります。
6. 討論
どのアルゴリズムを使用する必要がありますか? 答えは:それは異なります。
ブルートフォースアプローチは、3つすべての中で最も効率が悪いですが、唯一の方法である場合もあります。 ツリーがリレーション別に並べられていて、別のリレーションのランクを見つけたい場合、唯一のオプションはブルートフォースです。 (一般的に)何も教えてくれないので、ツリー全体をトラバースする必要があります。
ツリーを順序付ける同じ関係のランクを決定する場合、2番目と3番目のアプローチはブルートフォースよりもうまく機能します。 size属性でノードを拡張できない場合は、2番目のアルゴリズムを使用する必要があります。 可能であれば、3番目の方法を選択する必要があります。
バランスの取れたツリーを使用するかどうかは、複数の要因によって異なります。 1番目と2番目のアルゴリズムはバランスの取れたツリーを必要としませんが、バランスを保つと、ツリーに対して実行する他の操作が役立つ場合があります。 3番目のアプローチは、ツリーのバランスをとることから最も恩恵を受けます。 しかし、
7. 結論
この記事では、二分探索木でノードのランクを決定する3つの方法を紹介しました。 1つは、入力ツリーのバランスが取れているかどうかです。 それ以外の場合、3つすべてが最悪の場合ですが、2つの非ブルートフォースアプローチは通常、実際のブルートフォース方式よりも高速です。