ソートされた整数配列が与えられた場合、バイナリ検索ツリーはどのようにそれから形成できますか？

Question

私は配列[3,18,15,25,26]を持っているとします。可能なバイナリ検索ツリーはいくつありますか？

Answer 1

MicSimがリンクしている質問を見ても、私はまだそれに満足していなかったので、私はそれを自分で見始めました。ここで私が思いついたのは...

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

最初に低いカウントインスタンスを解決することで、より高いカウントソリューションを構築することができます。

C(n)を使用して、n個のノードの可能な組み合わせの総数を表すカタロニア数を表します。

がうまくいけば、これら二つは明白です：

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

C（2）もかなり明白であるが、それは構築することができ、その者はそれをやらせます。ルートノードを選択する方法は2つあります。 1つは子カウント（左：右）を1:0とし、もう1つは0:1です。したがって、最初の可能性はC(1)*C(0) = 1*1 = 1です。 2番目はC(0)*C(1) = 1*1 = 1です。それらをまとめて合計すると、私たちは

まだエキサイティングです。今度は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 

4ノードが3:0、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つと一致しました。

Answer 2

N個のキーで作成できるバイナリ検索ツリーの数は、N番目のcatalan numberで与えられます。

また、この質問を参照：The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?を

Answer 3

アレイのノードのいずれかが、BSTのルートであってもよいが、各ルートのために、別個の探索木の数は左の組合せ（製品）と右部分配列。だから、

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

あなたが最初の数nにこの機能を評価して、閉じた形を見つけるためにOn-Line Encyclopedia of Integer Sequences™ (OEIS)順序を調べることができます。