给定一个排序的整数数组,如何从它形成二进制搜索树？

Question

考虑我有一个数组[3,18,15,25,26],可以从中形成多少个可能的二叉搜索树？

Answer 1

在看了MicSim链接的问题之后,我仍然对此不满意,所以我开始自己查看.这就是我想出来的......

每棵树可以被认为是具有父根节点的两棵树.如果您分别知道两个子分支的可能组合的数量,则具有该根节点的总组合是子组合的乘积.

我们可以通过首先解决较低计数实例来开始构建更高计数的解决方案.

我将C(n)用来表示n个节点的总可能组合,加泰罗尼亚数.

希望这两个是显而易见的:

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

C(2)也很明显,但它可以构建,所以让我们这样做.有两种方法可以选择根节点.一个留下孩子的数量(左:右)1:0和另一个0:1.所以,第一种可能性是C(1)*C(0) = 1*1 = 1.第二是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

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

希望有两件事情开始变得明显.首先,这将很快变得麻烦.其次,我所描述的,以相当冗长的方式,是维基页面上的递归关系表示.

我不知道这是否有帮助,但它帮助我完成了练习,所以我想我会分享.我开始时并没有尝试重新创建递归关系,因此我的结果与现有方法之一相匹配.

Answer 2

可以使用N个密钥创建的二叉搜索树的可能数量由第N个加泰罗尼亚数给出.

另请参阅此问题:可以使用N个键创建的二叉搜索树的可能数量由第N个加泰罗尼亚语编号给出.为什么？

Answer 3

阵列的任何节点都可以是BST的根,并且对于每个根,不同搜索树的数量是左和右子阵列的组合(产品).所以,

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

您可以为前几个n评估此函数,然后在整数序列™在线百科全书(OEIS)中查找序列以查找封闭形式.