计算Treaps

Question

考虑计算结构上不同的二叉搜索树的数量的问题:

给定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 ... N的不同treap的数量,优先级为1 .. N.如果它们在相对于密钥或优先级的结构上不同,则两个treap是不同的(请继续阅读以进行说明).

我一直试图找出一个可以解决这个问题的公式或算法,但我还没有成功.这是我注意到的:

1. 对于这些问题的答案n = 2,并n = 3似乎是2和6,基于我在纸上画树木.
2. 如果我们忽略了表示treaps的部分也可能与节点的优先级不同,那么问题似乎与仅计算二进制搜索树相同,因为我们将能够为每个BST分配优先级,以便它也尊重堆不变量.我没有证明这一点.

3. 我认为困难的部分是考虑到在不改变结构的情况下置换优先级的可能性.例如,考虑这个treap,其中节点表示为(key, priority)对:

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

   我们可以在保持堆不变的情况下置换第二级和第三级的优先级,因此即使没有键切换位置,我们也可以获得更多解决方案.这对于更大的树木来说可能更加丑陋.例如,这与上面的不同:

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

如果有人可以就如何处理这个问题分享任何想法,我将不胜感激.当我想到它时,这似乎是一个有趣的计数问题.也许别人也想过这件事,甚至解决了!

Answer 1

有趣的问题!我相信答案是N阶乘!

给定树结构,只有一种方法可以填充二叉搜索树键值.

因此,我们需要做的就是计算堆的不同数量.

给定堆,考虑树的有序遍历.

这对应于数字1到N的排列.

现在给出{1,2 ...,N}的任何排列,你可以按如下方式构造一个堆:

找到最大元素的位置.左边的元素构成左子树,右边的元素构成右子树.通过找到最大元素并在那里分裂来递归地形成这些子树.

这会产生堆,因为我们总是选择max元素,并且该堆的有序遍历是我们开始的排列.因此,我们有一种从堆堆到permutaion并返回唯一的方式.

因此所需的数字是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)

有关更正式的证据:

如果H _N是1 ... N上的堆数,那么我们就有了

H _N = Sum_ {L = 0至N-1} H _L*H _N-1-L*(N-1选择L)

(基本上我们选择最大值并分配给root.选择左子树的大小,然后选择那么多元素并在左右两侧递归).

现在,

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

如果H _n = n!对于0≤n≤k

然后H _{K + 1} =Sum_{L=0 to K} L! * (K-L)! * (K!/L!*(K-L)!) = (K+1)!