计算所有结构上不同的二叉树的数量的时间复杂度是多少? [英] What would be the time complexity of counting the number of all structurally different binary trees?

问题描述

使用此处提供的方法: http://cslibrary.stanford.edu/110 /BinaryTrees.html#java

Using the method presented here: http://cslibrary.stanford.edu/110/BinaryTrees.html#java

12. countTrees() Solution (Java)
/**
 For the key values 1...numKeys, how many structurally unique
 binary search trees are possible that store those keys?

 Strategy: consider that each value could be the root.
 Recursively find the size of the left and right subtrees.
*/
public static int countTrees(int numKeys) {
  if (numKeys <=1) {
    return(1);
  }
  else {
    // there will be one value at the root, with whatever remains
    // on the left and right each forming their own subtrees.
    // Iterate through all the values that could be the root...
    int sum = 0;
    int left, right, root;

    for (root=1; root<=numKeys; root++) {
      left = countTrees(root-1);
      right = countTrees(numKeys - root);

      // number of possible trees with this root == left*right
      sum += left*right;
    }

    return(sum);
  }
} 

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

I have a sense that it might be n(n-1)(n-2)...1, i.e. n!

如果使用回忆器，复杂度是否为O(n)?

If using a memoizer, is the complexity O(n)?

推荐答案

节点数为n的完整二叉树的数量为第n个加泰罗尼亚语数字.加泰罗尼亚语数字的计算方式为

The number of full binary trees with number of nodes n is the nth Catalan number. Catalan Numbers are calculated as

这是复杂度O(n).

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

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

这篇关于计算所有结构上不同的二叉树的数量的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！