n个不同元素上的二叉搜索树的数量
sid*_*uff 15 algorithm math binary-tree proof binary-search-tree
可以从n个不同的元素构造多少个二叉搜索树？我们怎样才能找到一个经过数学验证的公式呢？
示例: 如果我们有3个不同的元素,比如说1,2,3,则有5个二叉搜索树.
tem*_*def 41
给定n个元素,可以从这些元素产生的二叉搜索树的数量由第n个加泰罗尼亚数(表示为C n)给出.这等于
直观地说,加泰罗尼亚数字表示可以通过以下方式从n个元素中创建结构的方式的数量:
- 将元素排序为1,2,3,...,n.
- 选择其中一个元素作为枢轴元素.这将剩余的元素分成两组 - 在元素之前和之后的元素.
- 从这两组中递归构建结构.
- 将这两个结构与您移除的一个元素组合在一起,以获得最终结构.
此模式完全匹配您可以从一组n个元素构建BST的方式.选择一个元素作为树的根.所有较小的元素必须向左移动,所有较大的元素必须向右移动.然后,您可以从左侧和右侧的元素中构建较小的BST,然后将它们与根节点融合在一起以形成整体BST.使用n个元素执行此操作的方法数由C n给出,因此可能的BST数由第n个加泰罗尼亚数给出.
希望这可以帮助!
我确信这个问题不仅仅是使用数学公式计算.我花了一些时间编写程序以及计算背后的解释或想法.
我尝试用递归和动态编程来解决它.希望这可以帮助.
该公式已存在于上一个答案中:
因此,如果您有兴趣学习解决方案并理解apporach,您可以随时查看我的文章计数二元搜索树由N个独特元素创建