10

私が配列を持っていると考えてください、それから[3,18,15,25,26]いくつの可能な二分探索木を形成することができますか？

4

3 に答える 3

16

MicSim でリンクされた質問を見た後、それでも満足できなかったので、自分で調べ始めました。これが私が思いついたものです...

各ツリーは、親ルート ノードを持つ 2 つのツリーと考えることができます。2 つの子分岐の可能な組み合わせの数が別々にわかっている場合、そのルート ノードを持つ組み合わせの合計は、子の組み合わせの積になります。

最初に数の少ないインスタンスを解決することで、数の多いソリューションの構築を開始できます。

C(n)n 個のノードの可能な組み合わせの合計をカタロニア語数で表すために使用します。

うまくいけば、これら2つは明らかです：

C(0) = 1
C(1) = 1

C(2)もかなり自明ですが、ビルドできるのでやってみましょう。ルート ノードを選択するには、2 つの方法があります。1 つは子カウント (左:右) を残し、もう 1 つは の子カウント (左:右) を残し1:0ます0:1。というわけで、1つ目の可能性はC(1)*C(0) = 1*1 = 1. そして2つ目はC(0)*C(1) = 1*1 = 1。それらを合計すると、

C(2) = 2

まだエキサイティングなことは何もありません。それでは、3つのノードを実行しましょう。ルート ノードを選択するには 3 つの方法があるため、3 つの子グループが作成されます。可能性のあるグループは2:0、1:1および0:2です。

以前の定義に基づいて、C(3)と書くことができますC(2)*C(0) + C(1)*C(1) + C(0)*C(2) = 2*1 + 1*1 + 1*2 = 2+1+2 = 5。

C(3) = 5

3:04 つのノードには、、、およびの子グループが2:1あり1:2ます0:3。したがって、 のC(4)ように記述できますC(3)*C(0) + C(2)*C(1) + C(1)*C(2) + C(0)*C(3) = 5*1 + 2*1 + 1*2 + 1*5 = 5+2+2+5 = 14。

C(4) = 14

うまくいけば、2 つのことが明らかになり始めています。まず、これはすぐに面倒になり始めます。第二に、私がかなり長々と説明したのは、wiki ページでの再帰関係の表現です。

これが役立つかどうかはわかりませんが、演習を進めるのに役立ったので、共有したいと思いました. 最初は再帰関係を再現しようとしていたわけではないので、結果が既存の方法の 1 つと一致したのは良かったです。

于 2012-07-30T16:46:45.827 に答える
7

N 個のキーで作成できる二分探索木の可能な数は、N 番目のカタロニア語数によって与えられます。

この質問も参照してください: N 個のキーで作成できる二分探索木の可能な数は、N 番目のカタロニア語数で与えられます。なんで？

于 2012-07-30T15:15:11.073 に答える
5

配列のノードのいずれかが BST のルートになることができ、各ルートの個別の検索ツリーの数は、左と右のサブアレイの組み合わせ (積) です。そう、

BSTCount(0) = 1
BSTCount(n) = sum_{i = 1}^{n} BSTCount(i-1) * BSTCount(n-i)

この関数を最初の数 n について評価し、オンライン エンサイクロペディア オブ 整数シーケンス™ (OEIS)でシーケンスを検索して、閉じた形式を見つけることができます。

于 2012-07-30T15:16:47.093 に答える