具有n个项目的每个可能子集的二进制搜索树的最大数量是多少？ [英] what is the maximum number of binary search trees with every possible subset of n items?

问题描述

假设列表中有n个元素。我想知道每个可能的列表子集可以有多少个BST。我搜索过，加泰罗尼亚语号码没有答案，因为它没有告诉我们每个子集。

Suppose there are n elements in a list. I want to know that how many BSTs are possible with every possible subset of list. I have searched and catalan number is no the answer because it does not tell us about every subset.

推荐答案

看起来像是一个学校作业，问题不明确并且完全定义了，所以，对不起：没有完整的解决方案。



这个问题根本没有意义。列表无关紧要。如果你选择n< N个元素，N也变得无关紧要，只有n是必不可少的。这个问题简化为：给定n个对象，可以从这些元素构建多少个不同的二叉搜索树？提示：每个特定的树实例取决于元素属性，定义的排序条件以及将它们输入填充树的算法的顺序。此外，由于明显的原因，一些人口订单会给出相同的树木，有些则不同。



现在，这个问题如何被表述为算法问题？也许，真正的问题是：如何创建一个算法来计算由给定元素集生成的所有可能的二叉搜索树？这个问题比较简单。你有一些提示，不是你可以尝试找到解决方案。怎么样尝试并问你更多问题？

-SA

It looks like a school assignment, and the problem is not clearly and fully defined, so, sorry: no complete solution for you.

The question simply makes no full sense. List is irrelevant. If you select some subset of n < N elements, N becomes also irrelevant, only n is essential. The question is reduced to this one: given n objects, how many different binary search trees can be built from those elements? The hint: each particular tree instance depends on the element properties, ordering condition defined and order of feeding them into the algorithm populating the tree. Moreover, by apparent reasons, some orders of population will give identical trees, and some are different.

Now, how this question can be formulated as the algorithm question? Perhaps, the real problems is: how to create an algorithm for calculating all possible binary search trees generated by a given set of elements? This problem is simpler. You got some hints, not you can try to find a solution. How about trying it and asking more questions if you stuck?

—SA

这篇关于具有n个项目的每个可能子集的二进制搜索树的最大数量是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！