Assignment #2: binary search trees (BST)

Programming Part

You should be familiar with binary search trees (BST) from previous courses. Given an insertion sequence, like the one illustrated on page 402 of the text, there is only one BST that can arise. On the other hand given a BST TT, there can be many difference insertion sequences that give the same tree TT.

In this assignment you will write a program that takes as input a permutation of 1,2,…,n1,2,…,n. Repeatedly inserting the elements of this permutation into an initially empty tree results in a BST TT. Your program is to output the number of different permutations that would give this same tree TT. As a simple example, the permutation 2,1,32,1,3 results in a tree whose root is 2 and with left and right children 1 and 3, respectively. Since the permutation 2,3,12,3,1 also gives this same tree, the result in this case is that there are 2 trees.

The input file will consist of an integer mm followed by mm cases. Each case is specified by an integer nn followed by some permutation of 1,2,…,n1,2,…,n. Since the numbers involved can get quite large, you should only output the last 8 digits of the answer. Be careful of integer overflow.

Sample input:
4
5
2 1 4 3 5
4
2 4 1 3
12
1 2 3 4 5 6 7 8 9 10 11 12
3
2 1 3
Sample output:
8
3
1
2
You will have a lot of leeway in this assignment about how you write the program, but you must adhere to the following outline. You are free to write your own classes, methods, and variables.

public class CountBinarySearch {

private long theCount;

CountBinarySearch( Scanner in ) {
// FOR YOU TO WRITE
}

public long getCount() { return theCount; }

public static void main ( String[] args ) {
// SIMILAR TO HOW WE WILL CALL YOUR PROGRAM
Scanner in = new Scanner( System.in );
int cases = in.nextInt();
for (int c=0; c<cases; ++c) {
CountBinarySearch cbs = new CountBinarySearch( in );
System.out.println( cbs.getCount() );
}
}

}
What to turn in: Submit a file CountBinarySearch.java. Testing will be automated. You will receive zero marks if you code does not compile. You may assume that the input is valid. Your code will also be judged on its efficiency.

Written part:

Let TT be a binary tree with root rr, left subtree LL, right subtree RR. Denote by |T||T|, the number of nodes in tree TT. Write a recurrence relation for C(T)C(T), the number of binary search tree labellings, as in the programming part above. Write a recurrence relation (including base cases, of course) for C(T)C(T). NOTE: It will be a good idea to do this problem before tackling the programming part.
In the style of the sorting handout, give a tree (graph) of posets for sorting 5 elements in 7 comparisons. What is the average number of comparisons used by your method, assuming that all 5!5! permutations are equally likely?
An inversion in a sequence is an out-of-order pair; i.e., i<ji<j but aiajaiaj. Inversions are discussed briefly in the book on page 252. For example, the sequence (5,3,2,1,45,3,2,1,4) has 7 inversions.
What is the minimum number of inversions of a permutation of 1,2,…,n1,2,…,n? What is the maximum number of inversions of a permutation of 1,2,…,n1,2,…,n?
Explain carefully how to use red-black trees to compute the number of inversions in a permutation time O(nlogn)O(nlog⁡n). Effectively, you may need to modify the code for Algorithm 3.4 on page 439. Explain in detail any changes that you would make to put.