如果有 N 个节点，有多少种不同的二进制搜索树和二进制搜索树？

对于二叉树: 没有必要考虑树节点值，我只对带有“ N”节点的不同树拓扑感兴趣。

对于二叉查找树: 我们必须考虑树节点值。

196934 次浏览
小开

Eric Lippert recently had a very in-depth series of blog posts about this: "Every Binary Tree There Is" and "Every Tree There Is" (plus some more after that).

In answer to your specific question, he says:

The number of binary trees with n nodes is given by the Catalan numbers, which have many interesting properties. The nth Catalan number is determined by the formula (2n)! / (n+1)!n!, which grows exponentially.

小开
最佳答案

I recommend this article by my colleague Nick Parlante (from back when he was still at Stanford). The count of structurally different binary trees (problem 12) has a simple recursive solution (which in closed form ends up being the Catalan formula which @codeka's answer already mentioned).

I'm not sure how the number of structurally different binary search trees (BSTs for short) would differ from that of "plain" binary trees -- except that, if by "consider tree node values" you mean that each node may be e.g. any number compatible with the BST condition, then the number of different (but not all structurally different!-) BSTs is infinite. I doubt you mean that, so, please clarify what you do mean with an example!

小开 
(2n)!/n!*(n+1)!
小开

Different binary trees with n nodes:

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

where C=combination eg.

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
小开

  1. Total no of Binary Trees are = enter image description![enter image description here

  2. Summing over i gives the total number of binary search trees with n nodes. enter image description here

The base case is t(0) = 1 and t(1) = 1, i.e. there is one empty BST and there is one BST with one node. enter image description here

So, In general you can compute total no of Binary Search Trees using above formula. I was asked a question in Google interview related on this formula. Question was how many total no of Binary Search Trees are possible with 6 vertices. So Answer is t(6) = 132

I think that I gave you some idea...

小开

The number of binary trees can be calculated using the catalan number.

The number of binary search trees can be seen as a recursive solution. i.e., Number of binary search trees = (Number of Left binary search sub-trees) * (Number of Right binary search sub-trees) * (Ways to choose the root)

In a BST, only the relative ordering between the elements matter. So, without any loss on generality, we can assume the distinct elements in the tree are 1, 2, 3, 4, ...., n. Also, let the number of BST be represented by f(n) for n elements.

Now we have the multiple cases for choosing the root.

  1. choose 1 as root, no element can be inserted on the left sub-tree. n-1 elements will be inserted on the right sub-tree.
  2. Choose 2 as root, 1 element can be inserted on the left sub-tree. n-2 elements can be inserted on the right sub-tree.
  3. Choose 3 as root, 2 element can be inserted on the left sub-tree. n-3 elements can be inserted on the right sub-tree.

...... Similarly, for i-th element as the root, i-1 elements can be on the left and n-i on the right.

These sub-trees are itself BST, thus, we can summarize the formula as:

f(n) = f(0)f(n-1) + f(1)f(n-2) + .......... + f(n-1)f(0)

Base cases, f(0) = 1, as there is exactly 1 way to make a BST with 0 nodes. f(1) = 1, as there is exactly 1 way to make a BST with 1 node.

Final Formula

小开

If given no. of Nodes are N Then.

Different No. of BST=Catalan(N)
Different No. of Structurally Different Binary trees are = Catalan(N)

Different No. of Binary Trees are=N!*Catalan(N)

小开

binary tree :

No need to consider values, we need to look at the structrue.

Given by (2 power n) - n

Eg: for three nodes it is (2 power 3) -3 = 8-3 = 5 different structrues

binary search tree:

We need to consider even the node values. We call it as Catalan Number

Given by 2n C n / n+1

小开

The correct answer should be 2nCn/(n+1) for unlabelled nodes and if the nodes are labelled then (2nCn)*n!/(n+1).

小开

  • Total number of possible Binary Search Trees with n different keys = 2nCn / (n + 1) 

    For n = 1  --> 1 Binary Search Tree is possible.
For n = 2  --> 2 Binary Search Trees are possible.
For n = 3  --> 5 Binary Search Trees are possible.
For n = 4  --> 14 Binary Search Trees are possible.
For n = 5  --> 42 Binary Search Trees are possible.
For n = 6  --> 132 Binary Search Trees are possible.```

  • And Total number of possible Binary Trees with n different keys = (2nCn / (n + 1)) * n!

    For n = 4 --> 336 Binary Search Trees are possible.


提交答案