[tree] ノード数が「N」の場合、バイナリ検索木とバイナリ検索木はいくつありますか?


3 Answers

  1. バイナリツリーの総数=

  2. iを合計すると、n個のノードを持つバイナリ検索ツリーの総数が求められます。

基本ケースはt(0)= 1であり、t(1)= 1であり、すなわち1つの空のBSTがあり、1つのノードを有する1つのBSTが存在する。

したがって、一般に、上記の公式を使用してバイナリ検索ツリーの合計数を計算することができます。 私はGoogleのインタビューでこの式に関連する質問をしました 。 質問は、6つの頂点でバイナリ検索ツリーの合計数がどれだけ可能かという質問でした。 だから答えはt(6)= 132

私はあなたにいくつか考えを与えたと思う...

Question

バイナリツリーの場合:ツリーノードの値を考慮する必要はありません。「N」ノードを持つ異なるツリートポロジにのみ関心があります。

バイナリ検索ツリーの場合:ツリーノードの値を考慮する必要があります。




n個のノードを持つ異なるバイナリツリー:

(1/(n+1))*(2nCn)

ここで、C =組み合わせ(例えば、

n=6,
possible binary trees=(1/7)*(12C6)=132



The number of possible binary search tree with n nodes (elements,items) is

=(2n C n) / (n+1) = ( factorial (2n) / factorial (n) * factorial (2n - n) ) / ( n + 1 ) 

where 'n' is number of nodes  (elements,items ) 

Example :

for 
n=1 BST=1,
n=2 BST 2,
n=3 BST=5,
n=4 BST=14 etc



指定されていない場合。 ノードの数はNです。

異なるBST =カタロニア語(N)
構造的に異なる2進木の数が異なる=カタロニア語(N)

二分木の数がNである!*カタロニア語(N)




Related