tem*_*def 18 algorithm math permutation binary-search-tree data-structures
之前的这个问题询问了将值1-7插入到二叉搜索树中的方法有多少,这将导致以下树:
4
/ \
2 6
/ \ / \
1 3 5 7
(顺便说一句,答案是80).
更一般地假设您获得了一个包含一组值的任意BST,并且想知道有多少可能的方法将这些值插入到最终生成结果树的BST中.有没有一种有效的算法来确定这个？
谢谢!
tem*_*def 27
我们可以使用聪明的递归算法来解决这个问题.
作为我们的基本情况,如果给出一个空树,那么只有一种方法可以构建该树 - 不要插入任何值.
对于递归情况,我们假设你有一个看起来像这样的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
...
既然给定了构建L和R的任何序列S L和S R我们可以按任何顺序交织它们,我们可以写出一个很好的公式,用于构建一个以v为根的树的序列数,L为其左子树,R为右子树:
#ways =(S L和S R的#surve)×(#可能的S L s)×(#可能的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's和n R开始,那么不同排列的数量就会变回
(m + n)!
-------- = (m + n) choose m
m! n!
这是因为有(m + n)!重新排序Ls和Rs的可能方法,如果它们都是不同的.因为它们不是,每个订单都计算在内!N!太多次了,因为我们可以无法区分L'和R'无法区分.考虑这个的另一种方法是考虑交错中的集合{1,2,3,...,m + n},然后选择m来填充第一个序列中的元素,隐式填充其余的元素来自正确的序列.
好的......我们现在有办法确定交织两个长度为m和n的序列的方式的数量.因此,我们有以下内容:
#ways =(S L和S R的#surve)×(#可能的S L s)×(#可能的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),虽然算法运行,因为随着数量越来越大,以这些数字相乘在一起所需的工作将快速增长.
希望这可以帮助!