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つの非ブルートフォースアプローチは通常、実際のブルートフォース方式よりも高速です。