可能なバイナリ検索ツリーの番号を見つける

Question

と入力します。1,2,3,4,5,6,7と入力します。二分探索木の高さが6であるような可能な二分探索木の総数を求めなければならない。

答えはです。しかし、私は答えを数学的に推論するためのパターンを見つけることができません。すべての可能性のある木を描く無理な力だけでは不可能です。

考えられるツリーの簡単な例の1つは、キーが昇順と降順で挿入されているスキューの不均衡なツリーです。両方の木は高さ6のでしょう。しかし、どのようにに達するには64？

Answer 1

これは構造によって証明できます。

F（N）= n+1番号
請求の高さnとバイナリ検索ツリーの数、と言うことができます：F(n) = 2^n

証明：今

F(0) = 1 (by construction) 
F(1) = 2 (by construction) 

、Fを算出する（nは）、最小数または最大数のいずれかをツリーのルートにすることができます。

したがって、（最小の番号がルートの場合）残りのn番号が（最大数は、ルートである場合）、左の部分木に配置されなければならない、または右う

F(n) = 2*F(n-1) 
F(n) = 2^n