考虑计数结构上不同二叉搜索树的：
由于N，查找包含值1结构不同的二叉搜索树的数量。N
它是pretty的容易得到的算法解决了这个：固定每一个可能的数字，在根，然后递归求解左和右子树的问题：
countBST（numKeys）
如果numKeys＆LT; = 1
返回1
其他
结果= 0
对于i = 1 .. numKeys
leftBST = countBST（I - 1）
rightBST = countBST（numKeys - I）
结果+ = leftBST * rightBST
返回结果
我最近一直在自己熟悉与 treaps 和我提出这样的问题：我自己
由于N，查找包含值1 ... N与优先级不同的treaps数量1 .. N.两个treaps是不同的，如果他们是相对于无论是键或优先级（读澄清）结构不同。
我一直在试图找出一个公式或一种算法，现在可以解决这个问题了一段时间，但我一直没成功。这就是我注意到，虽然：
的答案 N = 2 和 N = 3 似乎是 2 和 6 的基础上，我画在纸上的树。
如果我们忽略的部分，上面写着treaps也可以是相对于节点的优先级不同，这个问题似乎是相同的计算只是二叉搜索树，因为我们将能够分配优先级，以每BST这样它也尊重堆不变。我还没有证实这虽然。
我觉得最困难的部分是占重排的重点不改变结构的可能性。例如，考虑这个树堆，这里的节点是重新presented为（按键，优先级）对：
（3,5）
/
（2,3）（4，4）
/
（1,1）（5，2）
我们可以重排第二和第三级的优先次序，同时仍保持堆不变，所以我们获得更多的解决方案，即使没有键开关的地方。这可能会变得更大树丑陋。例如，这是由上面的一个不同的树堆
（3,5）
/
（2,4）（4，3）//交换优先级
/
（1,1）（5，2）
我倒是AP preciate如果任何人都可以分享关于如何处理这个任何想法。这似乎是一个有趣的计算问题时，我想过这个问题。也许有人对此太过，甚至解决了吧！别人的思想
解决方案有趣的问题！我相信答案是N个因子！
给定一个树状结构，有填补了二叉搜索树键值只有一个办法。
因此，我们需要做的是计算不同数堆。
由于堆，考虑一个在序遍历树。
这对应于编号1的至N的置换。
现在给出任何置换{1,2，...，N}，你可以构造一个堆如下：
查找最大元件的位置。这些元素在其左边形态左子树和元素，其右侧形成右子树。这些子树通过查找最大元素和分割那里递归形成
这产生了一个堆，因为我们总是选择最大元素和中序遍历的堆是我们开始与置换。因此，我们有从堆去一个permutaion和背部独特的方式。
因此所需的数目是N！
作为一个例子：
5
/
3 4在序遍历 - ＆GT; 35142
/
1 2
现在有35142.最大的开始是5，那么3是左子树和142是正确的。
5
/
{3} 142
在142，4为最大，1左2是正确的，所以我们得到
5
/
3 4
/
1 2
要填补这个二进制搜索键的唯一方法是：
（2,5）
/
（1,3）（4,4）
/
（3,1）（5,2）
有关一个更加正式的证明：
☆如果H N 是堆的数量在1 ... N，那么我们有
^ h N = Sum_ {L = 0到N-1} ^ h → * H N-1-L *（N- 1选择L）
（基本上我们挑最大并分配给根，选择左子树的大小，选择的许多元素和递归左和右）。
现在，
H0 = 1
H1 = 1
H2 = 2
H3 = 6
☆如果H N = N！当0乐; N'乐;氏/ P>
则H K + 1 = Sum_ {L = 0至K} L！ *（K-L）！ *（K！/ L！*（K-L）！）=（K + 1）！
Consider the problem of counting the number of structurally distinct binary search trees:
Given N, find the number of structurally distinct binary search trees containing the values 1 .. N
It's pretty easy to give an algorithm that solves this: fix every possible number in the root, then recursively solve the problem for the left and right subtrees:
countBST(numKeys)
if numKeys <= 1
return 1
else
result = 0
for i = 1 .. numKeys
leftBST = countBST(i - 1)
rightBST = countBST(numKeys - i)
result += leftBST * rightBST
return result
I've recently been familiarizing myself with treaps, and I posed the following problem to myself:
Given N, find the number of distinct treaps containing the values 1 .. N with priorities 1 .. N. Two treaps are distinct if they are structurally different relative to EITHER the key OR the priority (read on for clarification).
I've been trying to figure out a formula or an algorithm that can solve this for a while now, but I haven't been successful. This is what I noticed though:
The answers forn = 2 and n = 3 seem to be 2 and 6, based on me drawing trees on paper.
If we ignore the part that says treaps can also be different relative to the priority of the nodes, the problem seems to be identical to counting just binary search trees, since we'll be able to assign priorities to each BST such that it also respects the heap invariant. I haven't proven this though.
I think the hard part is accounting for the possibility to permute the priorities without changing the structure. For example, consider this treap, where the nodes are represented as (key, priority) pairs:
(3, 5)
/
(2, 3) (4, 4)
/
(1, 1) (5, 2)
We can permute the priorities of both the second and third levels while still maintaining the heap invariant, so we get more solutions even though no keys switch place. This probably gets even uglier for bigger trees. For example, this is a different treap from the one above:
(3, 5)
/
(2, 4) (4, 3) // swapped priorities
/
(1, 1) (5, 2)
I'd appreciate if anyone can share any ideas on how to approach this. It seemed like an interesting counting problem when I thought about it. Maybe someone else thought about it too and even solved it!
解决方案Interesting question! I believe the answer is N factorial!
Given a tree structure, there is exactly one way to fill in the binary search tree key values.
Thus all we need to do is count the different number of heaps.
Given a heap, consider an in-order traversal of the tree.
This corresponds to a permutation of the numbers 1 to N.
Now given any permutation of {1,2...,N}, you can construct a heap as follows:
Find the position of the largest element. The elements to its left form the left subtree and the elements to its right form the right subtree. These subtrees are formed recursively by finding the largest element and splitting there.
This gives rise to a heap, as we always choose the max element and the in-order traversal of that heap is the permutation we started with. Thus we have a way of going from a heap to a permutaion and back uniquely.
Thus the required number is N!.
As an example:
5
/
3 4 In-order traversal -> 35142
/
1 2
Now start with 35142. Largest is 5, so 3 is left subtree and 142 is right.
5
/
3 {142}
In 142, 4 is largest and 1 is left and 2 is right, so we get
5
/
3 4
/
1 2
The only way to fill in binary search keys for this is:
(2,5)
/
(1,3) (4,4)
/
(3,1) (5,2)
For a more formal proof:
If HN is the number of heaps on 1...N, then we have that
HN = Sum_{L=0 to N-1} HL * HN-1-L * (N-1 choose L)
(basically we pick the max and assign to root. Choose the size of left subtree, and choose that many elements and recurse on left and right).
Now,
H0 = 1
H1 = 1
H2 = 2
H3 = 6
If Hn = n! for 0 ≤ n ≤ k
Then HK+1 = Sum_{L=0 to K} L! * (K-L)! * (K!/L!*(K-L)!) = (K+1)!
相关推荐
最新文章