相关疑难解决方法(0)

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

给定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) …

   Run Code Online (Sandbox Code Playgroud)