Counting Treaps

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:

1. The answers for n = 2 and n = 3 seem to be 2 and 6, based on me drawing trees on paper.
2. 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.

3. 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 H_N is the number of heaps on 1...N, then we have that

H_N = Sum_{L=0 to N-1} H_L * H_N-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 H_n = n! for 0 ≤ n ≤ k

Then H_K+1 = Sum_{L=0 to K} L! * (K-L)! * (K!/L!*(K-L)!) = (K+1)!

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
}

You didn't actually define structural similarity for treaps -- you just gave examples. I'm going to assume the following definition: two trees are structurally different if and only if they have a different shape, or there exist nodes a (from tree A) and b (from tree B) such that a and b are in the same position, and the priorities of the children of a are in the opposite order of the priorities of the children of b. (It's obvious that if two treaps on the same values have the same shape, then the values in corresponding nodes are the same.)

In other words, if we visualize two trees by just giving the priorities on the nodes, the following two trees are structurally similar:

      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

but the following two trees are structurally different:

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

Thus for the treap problem, each internal node has 2 orderings, and these two orderings do not otherwise affect the shape of the tree. So...

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)
}