二叉搜索树数超过n个不同元素 [英] Number of binary search trees over n distinct elements

问题描述

有多少二叉搜索树可以从n个不同元素构成？我们怎样才能找到一个数学证明的公式呢？

  

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

// EN：<股利类=h2_lin>解决方案

给定的n个元素，可以从这些元素制成二进制搜索树的数量是由第n个Catalan数（表示为c <子> N ）。这等于

直观地，Catalan数重新present的方法可以创建一个结构出，其由以下述方式n个元素的数目：

• 排列元素为1，2，3，...，N。
• 在挑选这些元素作为支点元素使用的一个。这种分割剩余的元素分为两组 - 那些进来的元素之前和那些跟从
• 在递归构建结构出这两个群体中。
• 联合这两个结构和您一起除去以得到最终结构中的一个元素。

此模式完美匹配中，你可以从一组n个元素构建一个BST的方式。挑作为树的根以使用一种元素。所有的小元素必须向左走，和所有较大的元素必须去的权利。从那里，可以再构建较小BSTS出来的元素的左侧和右侧的，然后它们熔合一起根节点形成整体的BST。的方法可以与n个元素执行此数目被C <子> N 给出的，因此可能的BSTS数由第n加泰罗尼亚数给出。

希望这有助于！

How many binary search trees can be constructed from n distinct elements? And how can we find a mathematically proved formula for it?

Example: If we have 3 distinct elements, say 1, 2, 3, there are 5 binary search trees.

解决方案

Given n elements, the number of binary search trees that can be made from those elements is given by the nth Catalan number (denoted C_n). This is equal to

Intuitively, the Catalan numbers represent the number of ways that you can create a structure out of n elements that is made in the following way:

• Order the elements as 1, 2, 3, ..., n.
• Pick one of those elements to use as a pivot element. This splits the remaining elements into two groups - those that come before the element and those that come after.
• Recursively build structures out of those two groups.
• Combine those two structures together with the one element you removed to get the final structure.

This pattern perfectly matches the ways in which you can build a BST from a set of n elements. Pick one element to use as the root of the tree. All smaller elements must go to the left, and all larger elements must go to the right. From there, you can then build smaller BSTs out of the elements to the left and the right, then fuse them together with the root node to form an overall BST. The number of ways you can do this with n elements is given by C_n, and therefore the number of possible BSTs is given by the nth Catalan number.

Hope this helps!

这篇关于二叉搜索树数超过n个不同元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！