Card counting

Question

Consider the task of counting the number of structurally distinct binary search trees :

Given N, find the number of structurally distinct binary search trees containing 1 .. N

It is very easy to give an algorithm that solves this: fix all possible numbers in the root, and 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 met treaps recently , and I asked myself the following problem:

Given N, find the number of individual treaps containing the values ​​1 .. N with priorities 1 .. N. Two treaps are different if they are structurally different with respect to the key or priority (read for details).

I tried to figure out a formula or algorithm that could solve this for a while, but I was not successful. This is what I noticed, though:

• The answers for n = 2 and n = 3 seem to be 2 and 6 , based on the fact that I draw trees on paper.
• If we ignore the part that says that the treaps may also differ from the priority of the nodes, the problem seems to be identical to counting only the binary search trees, since we can prioritize each BST so that it also considers the heap invariant. However, I have not proved this.

• I believe that the difficult part takes into account the possibility of rearranging priorities without changing the structure. For example, consider this treap, where nodes are represented as (key, priority) pairs:

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

  We can transfer the priorities of both the second and third levels while maintaining the heap invariant, so we get more solutions, even if the keys do not switch. It probably becomes even more ugly for large trees. For example, this is different from the previous one:

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

I would be grateful if anyone could share ideas on how to approach this. This seemed like an interesting counting problem when I thought about it. Maybe someone else thought about it and even decided it!

Answer 1

Interest Ask! I believe the answer is N factorial!

For a tree structure, there is only one way to populate the key values ​​of a binary search tree.

Thus, all we need to do is to calculate a different amount of heap.

Given the heap, consider going around the tree in order.

This corresponds to a permutation of numbers from 1 to N.

Now, given any permutation {1,2 ..., N}, you can build the heap as follows:

Find the position of the largest element. Elements to the left of it of the left subtree and elements to the right of it form the right subtree. These subtrees are recursively formed by finding the largest element and splitting there.

This results in a heap, since we always select the max element and a traversal in the sequence of this heap is the permutation we started with. Thus, we have a clear path from the heap to the permutation and vice versa.

Thus, the required number is N !.

As an example:

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

Now start with 35142. The highest value is 5, so 3 is the left subtree, and 142 is correct.

  5 / \ 3 {142} 

In 142, 4 is the largest, and 1 is left, and 2 is right, so we get

  5 / \ 3 4 / \ 1 2 

The only way to populate binary search keys for this is:

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

---

For more formal proof:

If H _N is the number of heaps per 1 ... N, then we have that

H _N = Sum_ {L = 0 to N-1} H _L * H _N-1-L * (N- 1 select L)

(basically we select max and assign root. Choose the size of the left subtree and choose that many elements and recursion left and right).

Now,

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

If H _n = n! for 0? n? to

Then H _{K + 1} = Sum_{L=0 to K} L! * (KL)! * (K!/L!*(KL)!) = (K+1)! Sum_{L=0 to K} L! * (KL)! * (K!/L!*(KL)!) = (K+1)!

Answer 2

 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 did not actually define structural similarities for treaps - you just gave examples. I am going to accept the following definition: two trees are structurally different if and only if they have a different shape or there are nodes a (from tree A) and b (from tree B) such that a and b are in the same position, and children's priorities a are in the reverse order of children's priorities b. (Obviously, if two treaps on the same values ​​have the same shape, then the values ​​at the corresponding nodes are the same.)

In other words, if we visualize two trees simply by prioritizing 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 left child is still greater than 6 right child 5 left child is still greater than 5 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 task, each inner node has 2 orders, and these two orders do not otherwise affect the shape of the tree. So that...

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