binary-tree - 计算所有结构不同的二叉树的数量的时间复杂度是多少？

Question

使用此处介绍的方法：http: //cslibrary.stanford.edu/110/BinaryTrees.html#java

12. countTrees() 解决方案（Java）
/**
 对于键值 1...numKeys，有多少结构上唯一
 存储这些键的二叉搜索树是可能的吗？

 策略：认为每个值都可能是根。
 递归查找左右子树的大小。
*/
公共静态int countTrees（int numKeys）{
  如果（numKeys <=1）{
    返回（1）；
  }
  别的 {
    // 根将有一个值，剩下的都是
    // 左右各形成自己的子树。
    // 遍历所有可能是根的值...
    整数总和 = 0；
    int 左，右，根；

    for (root=1; root<=numKeys; root++) {
      左 = countTrees(root-1);
      对 = countTrees(numKeys - root);

      // 具有此根的可能树的数量 == left*right
      总和+=左*右；
    }

    返回（总和）；
  }
}

我有一种感觉，它可能是 n(n-1)(n-2)...1，即 n！

如果使用记忆器，复杂度是 O(n) 吗？

Answer 1

节点数为 n 的完整二叉树的数量是第 n 个加泰罗尼亚数。加泰罗尼亚数字计算为

这是复杂度O（n）。

http://mathworld.wolfram.com/BinaryTree.html

http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics

Answer 2

Not sure of how many hits to the look-up table is the memoized version going to make (which is definitely super-linear and will have the overheads of function calling) but with the mathematical proof yielding the result to be the same as nth Catalan number, one can quickly cook up a linear-time tabular method:

    int C=1;
    for (int i=1; i<=n; i++)
    {
        C = (2*(2*(i-1)+1)*C/((i-1)+2));
    }
    return C;

Note the difference between Memoization and Tabulation here

Answer 3

countTrees计算给定节点计数对该算法的调用次数很容易。经过几次试运行后，在我看来它需要 5*3^(n-2) 次调用 n >= 2，它的增长速度比 n! 慢得多。这个断言的证明留给读者作为练习。:-)

正如您所建议的，记忆化版本需要 O(n) 次调用。

顺便说一句，具有 n 个节点的二叉树的数量等于第 n 个加泰罗尼亚数。计算 C _n的显而易见的方法似乎都是线性的，因此记忆化的实现countTrees可能是最好的方法。