n个不同元素的二叉搜索树数量

Question

有多少个二叉搜索树可以由 n 个不同的元素构建？我们如何找到一个经过数学证明的公式？

例子： 如果我们有 3 个不同的元素，比如 1、2、3，那么就有 5 个二叉搜索树。

- siddstuff

---

可能与此相关。 - G. Bach

Answer 1

给定n个元素，可以从这些元素中制作的二叉搜索树数量由第n个Catalan number（表示为C_n）给出。这等于

直观地说，卡特兰数代表你可以用 n 个元素创建以下方式的结构的方法数量:

• 将元素排序为 1、2、3、...、n。
• 选择其中一个元素作为枢轴元素。这将把其余元素分成两组——在该元素之前和在该元素之后的元素。
• 对这两个组进行递归结构构建。
• 使用已删除的一个元素将这两个结构与原始的结构合并以获得最终的结构。

此模式完美匹配了从一组 n 个元素中构建 BST 的方式。选择一个元素作为树的根。所有较小的元素必须移到左侧，所有较大的元素必须移到右侧。从那里，您可以从左侧和右侧的元素中构建较小的 BST，然后将它们与根节点合并以形成整体 BST。使用 n 个元素可以完成这样做的方式数量由 C_n 给出，因此可能的 BST 数量由第 n 个卡特兰数给出。

希望这会有所帮助！

- templatetypedef

---

例如，对于节点10、10、10，二叉搜索树的数量为1。但是卡特兰数是5。但如果所有元素都不同，我认为也可以。 - Sukhanov Niсkolay

@SukhanovNiсkolay 对于10,10,10，BST的数量仍为5。但是树的形状将会不同。 - rents

Answer 2

我相信这个问题不仅仅是为了使用数学公式进行计算。我花了一些时间编写了程序，并解释了或者说阐述了同样计算的思路。我尝试了递归和动态规划两种方法来解决问题。希望这能有所帮助。公式已经在之前的答案中提到：如果你有兴趣学习解决方案并理解方法，你可以查看我的文章“从N个唯一元素创建二叉搜索树的计数”（链接：http://techieme.in/count-binary-search-trees/）。

- dharam

Answer 3

假设 T(n) 是 n 个元素的二叉搜索树数量。

给定 n 个不同的有序元素，编号为 1 到 n，我们选择 i 作为根节点。

这样就会有 (1..i-1) 在左子树中有 T(i-1) 种组合，在右子树中有 (i+1..n) 有 T(n-i) 种组合。

因此：

T(n) = sum_i=1^n(T(i-1) * T(n-i))

当然，T(1) = 1。

- Andrew Tomazos

---

可能值得一提的是，这个递归解决了第n个卡特兰数。 - templatetypedef

@templatetypedef：你知道如何从我展示的求和式推导出卡特兰数公式吗？ - Andrew Tomazos

@user1131467 这个总和应该恰好等于n+2个节点的多边形三角剖分数量，这也是我认识卡特兰数的方式。你固定一条边，让枢轴在其他n个顶点上漫游，这样就会留下两个大小为i-1和n-i的多边形。 - G. Bach

原来我的和有一个名字。它被称为"塞格纳递推关系"。在谷歌上搜索这个关键词加上卡塔兰数，就可以找到推导过程。 - Andrew Tomazos

@user1131467- 我知道的证明（使用生成函数）在维基百科网站上。实际上，那里有几个不同的证明，都相当不错。 - templatetypedef