22

这个较早的问题询问有多少种方法可以将值 1 - 7 插入到二叉搜索树中，这将产生以下树：

       4
     /   \
    2     6
   / \   / \
  1   3 5   7

（顺便说一句，答案是 80）。

更一般地假设您有一个任意的 BST，其中包含一组值，并且想知道有多少种可能的方法可以将这些值插入到最终生成结果树的 BST 中。是否有一种有效的算法来确定这一点？

谢谢！

4

2 回答 2

34

我们可以使用一个聪明的递归算法来解决这个问题。

作为我们的基本情况，如果给定一棵空树，则只有一种方法可以构建该树 - 不要插入任何值。

对于递归情况，假设您有一个如下所示的 BST：

              v
             / \
            L   R

这里，v 是根，L 和 R 分别是右子树。

如果我们想建立这个二叉搜索树，我们必须首先插入 v - 如果我们不这样做，v 就不会是根。在我们插入 v 之后，我们需要按顺序插入元素，这将导致子树 L 和 R 被重建。这里棘手的部分是我们不需要在构建 R 之前构建所有 L，反之亦然；我们可以从 L 中插入一些元素，然后从 R 中插入一些元素，然后从 L 中插入更多元素，然后从 R 中插入更多元素，等等。

不过幸运的是，我们可以做出一个有用的观察。假设 S L是一个元素序列，如果插入到 BST 中，则形成 BST L。类似地，让 S R是如果插入到 BST 中形成 BST R 的元素序列。如果我们考虑任何可能的交错序列 S L和 S R，我们将得到一个元素序列，如果将其插入到仅包含 v 的 BST 中，将构建树

   v
  / \
 L   R

例如，考虑这棵树：

       4
     /   \
    2     6
   / \   / \
  1   3 5   7

构建左子树（持有 1、2、3）的一种可能序列是 2、1、3。构建右子树的一种可能序列是 6、5、7。当插入 BST 时，这些序列的任何可能交错仅包含根节点 4，最终将构建上述 BST。例如，这些序列中的任何一个都可以工作：

 2, 1, 3, 6, 5, 7
 2, 6, 1, 5, 3, 7
 6, 5, 2, 1, 3, 7
 ...

由于给定任何序列 S L和 S R构建 L 和 R 我们可以以任何顺序将它们交错，我们可以写出一个很好的公式来计算将构建一棵以 v 为根、L 为它的树的序列数左子树，R为其右子树：

#ways = (# interleaves of S L and S R ) × (# possible S L s) × (# possible S R s)

如果你仔细想想，这个乘积中的最后两项可以通过递归地找到适用于左右子树的插入序列的数量来找到。这意味着如果我们能够计算出两个序列有多少可能的交错，那么我们可以通过递归地评估上述表达式来确定有多少可能的插入序列将构建给定的树！

那么有多少交错呢？如果给定两个长度为 m 和 n 的序列，其中没有重复，那么我们可以通过以下观察得出这些序列的交错数。考虑序列

L L L ... L R R R ... R
  m times     n times

该序列的任何排列都将返回一系列 Ls 和 Rs，其中 Ls 的数量等于长度为 m 的序列中的元素数量，Rs 的数量等于长度为 n 的序列中的元素数量. 我们可以将此序列解释为描述如何构建交错的一种方式——任何时候我们看到 L，我们从左侧序列中插入一个元素，并且任何时候我们看到 R，我们从右侧序列中插入一个元素。例如，考虑序列 4, 1, 0, 3 和 2, 7。那么置换 LLRLRL 给出了序列

 4, 1, 2, 0, 3, 7
 L  L  R  L  R  L

如果我们从 m L 和 n R 的序列开始，不同排列的数量返回为

(m + n)!
-------- = (m + n) choose m
 m!  n!

这成立是因为有 (m + n)！如果 Ls 和 Rs 都是不同的，则重新排序它们的可能方法。由于不是，因此每个订单都计为 m！嗯！太多次了，因为我们可以无差别地排列 L's 和难以区分的 R's。考虑这个问题的另一种方法是考虑交错中的索引集合 {1, 2, 3, ..., m + n}，然后选择其中的 m 个来填充第一个序列中的元素，隐式填充其余的带有来自正确序列的元素。

好的……我们现在有一种方法可以确定交织长度为 m 和 n 的两个序列的方法的数量。因此，我们有以下内容：

#ways = (# interleaves of S L and S R ) × (# possible S L s) × (# possible S R s)

= ((m + n) 选择 n) × (# 可能的 S L s) × (# 可能的 S R s)

其中 m 是左子树的元素个数，n 是右子树的元素个数。耶！

因此我们可以为这个算法写出伪代码：

function countInsertionOrderings(Tree t) {
    if t is null, return 1;
    otherwise:
       let m = numElementsIn(t.left);
       let n = numElementsIn(t.right);
       return choose(m + n, n) * 
              countInsertionOrderings(t.left) *
              countInsertionOrderings(t.right);
}

该算法总共执行 O(n) 次乘法，其中 n 是树中的节点数，并且每个节点只访问一次（假设 BST 中的元素数被缓存在每个节点上）。但是，这并不意味着算法在 O(n) 时间内运行，因为将这些数字相乘所需的工作将随着数字越来越大而迅速增长。

希望这可以帮助！

于 2013-06-15T00:35:20.263 回答
1

这是个有趣的问题。我在 python 中实现了这个想法，这种递归加记忆有很好的性能。“seq”是唯一整数的输入列表

def answer(seq):
    from math import factorial
    BStore = dict() # store binomsial coefficient
    Store = dict() # store the recusion step 
    def TreeGenerator(a,L): # for a given number a and a list L, this functions returns the left tree (a list) and the right tree (a list)
        LT = []
        RT = []
        for i in L:
            if i<a:
               LT.append(i)
            else:
               RT.append(i)
        solution = [LT,RT]
        return(solution)       
    def binomial_coefficient(n, k):
        d = n - k
        if d < 0:
           return(0)
        return(factorial(n) / factorial(k) / factorial(d))
    def binomial(n, k):
        if (n, k) in BStore:
           return(BStore[n, k])
        else:
           solution = binomial_coefficient(n, k)
           BStore[n, k] = solution
           return(solution)    
    def R(S): # recursion starts here
        if tuple(S) in Store:
           return(Store[tuple(S)])
        else:
           if len(S)<2:
              results = 1
           else:
              a = S[0]
              S = S[1:]
              Tree = TreeGenerator(a,S)
              R1 = R(Tree[0])
              R2 = R(Tree[1]) 
              results = binomial(len(R1)+len(R2), len(R2))*R1*R2             
        Store[tuple(S)] = results
        return(results)
     return(R(seq))
于 2016-06-13T20:43:13.550 回答