代码之家 › 专栏 › 技术社区 › IVlad

计数Treaps

combinatorics binary-tree math algorithm

IVlad · 技术社区 · 15 年前

考虑计算结构上不同的 binary search trees :

很容易给出一个算法来解决这个问题:确定根中所有可能的数字,然后递归地解决左子树和右子树的问题:

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 ,基于我在纸上画树。
如果我们忽略了表示treap相对于节点优先级也可能不同的部分,那么问题似乎就等同于只计算二叉搜索树,因为我们可以为每个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)
```

如果有人能分享一些关于如何处理这个问题的想法,我将不胜感激。当我想起来的时候,这似乎是一个有趣的计数问题。也许别人也想过,甚至解决了!

2 回复 | 直到 15 年前

Aryabhatta Aryabhatta 15 年前

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

给定一个树结构,只有一种方法可以填充二进制搜索树的键值。

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

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

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

这就产生了一个堆,因为我们总是选择max元素,遍历该堆的顺序就是我们开始的排列。因此,我们有一种从堆到置换再返回的方法。

    5
   / \
  3   4          In-order traversal ->   35142
     / \ 
     1  2

现在从35142开始,最大的是5,所以3是左子树,142是右子树。

    5
   / \
  3  {142}

在142中,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 *小时 _N-1-升

(基本上我们选择最大值并分配给根。选择左子树的大小,并选择许多元素(左、右递归)。

现在,

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

如果H _n

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

Ken Bloom 15 年前

def countBST(numKeys:Long):Long = numKeys match {
  case 0L => 1L
  case 1L => 1L
  case _ => (1L to numKeys).map{i=>countBST(i-1) * countBST(numKeys-i)}.sum
}

      7               7
   6      5        6      5
  4 3    2 1      2 1    4 3  <--- does not change the relative order
                                   of the children of any node
                                   6's left child is still greater than 6's right child
                                   5's left child is still greater than 5's right child

但以下两棵树在结构上是不同的:

      7               7
   5      6        6      5   <--- changes the relative order of the children
  4 3    2 1      4 3    2 1       of node 7

def countTreap(numKeys:Long):Long = numKeys match {
  case 0L => 1L
  case 1L => 1L
  case _ => 2 * countBST(numKeys-1) +  //2 situations when the tree has only 1 child
            2 * (2L to (numKeys-1)).map{i=>countBST(i-1) * countBST(numKeys-i)}.sum
            // and for each situation where the tree has 2 children, this node  
            // contributes 2 orderings the priorities of its children
            // (which is independent of the shape of the tree below this level)
}