異なる二分探索木の数と二分探索木の数を計算する方法

1. 概要

このチュートリアルでは、さまざまな二分探索木と二分探索木（BST）の数を計算する方法について学習します。また、これらの式の直感的な説明を紹介します。バイナリツリーとBSTのデータ構造に関する基本的な知識があることを前提としています。

2. 二分探索木と二分探索木

ご存知のように、 BSTは、重複する値を許可しない順序付けられたデータ構造です。ただし、バイナリツリーでは、値を2回以上繰り返すことができます。さらに、二分木は順序付けられていません。これらは、これら2つのデータ構造の主な違いです。

BSTを使用すると、その値をソートされた順序でトラバースできます。 Balanced BSTは、ツリーに対するすべての操作が時間計算量を持つことを保証します。そのため、プログラミングのさまざまな分野で適用されています。たとえば、赤黒木は自己平衡二分探索木です。これらは、JavaのTreeMapの内部実装として使用されます。二分木は操作を期待しないため、めったに使用されません（例：検索、挿入、検索）を効率的に実行します。

3. 多数の二分探索木

ツリーにノードがあるとします。これは、ノードの値として一意の番号が含まれていることを意味します。このセクションでは、単純な再帰式を定義します。これにより、サイズが構造的に異なる二分探索木の数がわかります。

3.1. 直感的な説明

ツリーには常にルートがあります。ルートを選択する方法はいくつかあります。覚えておくべき重要なことは、ツリー内のすべての要素が異なることです。したがって、一般性を失うことなく、要素は1から。までの数字のリストになる可能性があります。実際、この問題を解決する際に、私たちは自分たちがどんな要素を持っているかを本当に気にしません。主なアイデアは、それらがユニークであるということです。

ツリーのルートとして最小の要素を選択すると、左側のサブツリーにゼロ値を挿入できます。ただし、そうすると、そのような挿入はメインのBSTプロパティに違反します。左側のサブツリーのすべての値はルートよりも小さくなければならず、右側のサブツリーの場合はその逆になります。ただし、残りの値を右側のサブツリーに挿入できます。

一般化すると、ノードの場合、ノードを左側のサブツリーに挿入し、ノードを右側のサブツリーに挿入できます。また、1からまでのそれぞれに対して行うことができます。

これで、ルートが固定されている場合、さまざまなツリーを構築する方法の総数はになります。は異なる左側のサブツリーの数であり、は異なる右側のサブツリーの数です。再帰式を進めましょう。

3.2. 再帰的アプローチ

上記のステートメントを使用して、再帰式を作成できます。 ノードの異なる二分探索木の数とします。 1つのノードを含むツリーのさまざまなツリーの数が1であることに注意してください。つまり、1です。同様に、ツリーが空の場合、1つの可能なツリー（この空のツリーのみ）があり、。 2から始まるその他の場合：

それぞれ1、2、および3ノードのすべての可能な二分探索木を構築する例を見てみましょう。

お気づきかもしれませんが、3ノードの可能なBSTは5つだけです。しかし、3ノードの5つ以上の異なる二分木が存在します。セクション5で注意を払います。

4. カタラン数

最後に、異なるBSTの数がカタラン数であるという事実を紹介することに非常に近いです。この数値は、ポリゴンの三角形分割や有効なブラケットシーケンスなど、さまざまな組み合わせ問題でよく使用されます。カタラン数は、再帰的に定義されるオブジェクトの数を表す場合があります。この場合、カタラン数はです。

したがって、導入された再帰式はです。 proof は簡単ではなく、この記事の範囲外です。

5. 二分木の数

ここで、バイナリツリーに異なる値しかないものと仮定しましょう。二分探索木とは異なり、私たちのツリーには従わなければならない規則がありません。それで、それは私たちにとってどういう意味ですか？つまり、バイナリツリーのさまざまな構造ごとに、ノード値を再配置して他のツリーを取得することもできます。理解を深めるために、写真を見てみましょう。

これらの木はすべて構造的に互いに等しい。ノードの構造は同じです。ツリーにはルートと両方の子があります。ただし、さまざまな方法でノード値を再配置できます。それを行うには、単純なアルゴリズムに従うことができます。

ノードのツリーがあるとしましょう。まず、任意のノードを選択し、任意の値を割り当てます。次に、次のノードを選択します。次の値を割り当てるには、残っている値から選択します。最後に、最後のノードでは、値が1つだけ残るため、値を選択することはできません。

その結果、私たちの単純なアルゴリズムは、ノードとツリーの固定構造に対して、異なるツリーが存在する可能性があることを説明しています。

要約すると、異なる二分木の数はです。ただし、これはすべての要素が異なる場合にのみ当てはまります。そうでない場合、分子は少し異なって見えます。

5.1. 繰り返しのある順列

繰り返しがないため、順列の式の特殊なケースです。少し拡張します。

すべての値を一連の数値に収集できます。ここで、それらが区別されていない場合。そしてもしそうなら。それらの繰り返しの数にしましょう。ちなみに、繰り返しのある順列の式は次のようになります。

の場合、、、。と。

5.2. 異なるおよび構造的に異なる二分木の数

その結果、ノードの二分木の数の最終的な式はになります。ツリーの値の繰り返しです。ここで、。これは一般的な式であり、一意の値と一意ではない値を持つツリーに使用できます。

ただし、構造的に異なる二分木の数は異なる二分探索木の数と同じです。異なるBSTの数はカタラン数です。

6. 結論

この記事では、さまざまな二分探索木と二分探索木の数を計算する方法を学びました。さらに、組み合わせ論からいくつかの式を改訂しました。さらに、計算式の直感的な説明を紹介しました。ご覧のとおり、ツリーの構造が重要な場合もありますが、値は重要ではありません。これらは、適切な式を選択するための重要なポイントです。