algorithm - 数数挖掘

考虑计算结构上不同的binary search trees个数的问题：
给定n，查找包含值1的结构上不同的二进制搜索树的数目。n个
很容易给出一个算法来解决这个问题：修复根中的每个可能数字，然后递归地解决左子树和右子树的问题：

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

我最近一直在熟悉treaps，我向自己提出了以下问题：
给定n，查找包含值1的不同treap的数目。n优先级为1..n.如果两个treap相对于键或优先级在结构上不同，则它们是不同的（请继续阅读以获得澄清）。
我一直在试图找出一个公式或算法，可以解决这一段时间了，但我没有成功这就是我注意到的：
根据我在纸上画树的情况，n = 2和n = 3的答案似乎是2和6。
如果我们忽略了treaps相对于节点优先级也可能不同的部分，那么问题似乎与只计算二进制搜索树是相同的，因为我们可以为每个bst分配优先级，这样它也会尊重堆不变量。但我还没有证明。
我认为最困难的部分是在不改变结构的情况下考虑优先权的可能性。例如，考虑这个treap，其中节点表示为(key, priority)对：

          (3, 5)
          /    \
     (2, 3)    (4, 4)
     /              \
(1, 1)               (5, 2)

我们可以在保持堆不变的情况下排列第二层和第三层的优先级，因此即使没有密钥交换位置，我们也可以得到更多的解决方案。对于更大的树来说，这可能会更难看。例如，这是与上面的不同的treap：

          (3, 5)
          /    \
     (2, 4)    (4, 3) // swapped priorities
     /              \
(1, 1)               (5, 2)

如果有人能就如何解决这个问题分享一些想法，我将不胜感激当我想到这件事时，它似乎是一个有趣的计数问题。也许别人也想过，甚至解决了！

最佳答案

有趣的问题我相信答案是n阶乘！
给定一个树结构，只有一种方法可以填充二叉搜索树的键值。
因此，我们需要做的就是计算不同数量的堆。
给定一个堆，考虑按顺序遍历树。
这对应于数字1到N的排列。
现在给定{1,2…，N}的任何排列，您可以如下构造堆：
找到最大元素的位置。左边的元素构成左边的子树，右边的元素构成右边的子树这些子树是通过找到最大的元素并在那里分裂而递归形成的。
这就产生了一个堆，因为我们总是选择max元素，而堆的顺序遍历就是我们开始的排列。这样我们就有了一种从堆到置换再到唯一的返回的方法。
因此所需的数字是N！是的。
例如：

    5
   / \
  3   4          In-order traversal ->   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)

更正式的证明：
如果HN是1上的堆数…N，那么我们就有了
hn=和{l=0到n-1}hl*hn-1-l*（n-1选择l）
（基本上我们选择最大值并分配给根。选择左子树的大小，然后选择多个元素并在左和右递归）。
现在，

H0 = 1
H1 = 1
H2 = 2
H3 = 6

如果hn=n！对于0≤n≤k
则hk+1=Sum_{L=0 to K} L! * (K-L)! * (K!/L!*(K-L)!) = (K+1)!

关于algorithm - 数数挖掘，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3153620/