Description

For each of the following input sequences, draw the associated  left-leaning red-black binary search tree. Include the coloring of the edges in your figure. As an example, if the input was 4, 3, 1, 5, 2 you would draw:

1. 1, 3, 5, 7, 6, 4, 2
2. 4, 6, 8, 3, 1, 5, 7, 2
3. 1, 2, 3, 4, 5, 6, 7
4. 7, 6, 5, 4, 3, 2, 1

Task 2

The class ​BST.java​ contains an implementation of a binary search tree.

The class ​PerfectBST.java​ extends ​BST.java​ with one new constructor

PerfectBST(Key k[], Value v[])​ that constructs a perfectly balanced binary tree using (​k[i] ,v[i]​) as (key, value) pairs. You can assume that ​k[]​ is sorted in ascending order and that ​k[]​ and ​v[]​ are of the same length. Your task is to implement this constructor in the given file. Your code should have linear running time measured in the number of pairs.

Example:

If ​k[]​ consists of ​[a,b,c,d,e,f,g]​ then you should build the following tree (value fields are not shown):

If there are N numbers in ​k[]​ and N is an even number then you can either choose element N/2 or N/2+1 as the root element. This also applies recursively when selecting subroots.

Task 3

The median of sequence of  N numbers is the middle number if the numbers are sorted. If N is even then the median is the average of the two numbers in position N/2 and N/2+1 (if the numbers are sorted).

Example: The median of [1,5,2,3,7,6,4] is 4, while the median of [1,5,2,3,6,4] is 3.5.

Write a class ​MedianPQ.java​ that supports the two operations insert a floating point number and find median. Insert should run in ​logarithmic time and find​

median in ​constant time​. You can use the two classes ​MaxPQ.java​ and MinPQ.java​ for this assignment.

You can use the class ​MedianPQClient.java​ to test the program. This program reads floating point values from standard input and inserts these into the MedianPQ​ data structure. For each inserted value the current median value is printed.

Example: 1.0

Median = 1.0

5.0

Median = 3.0

2.0

Median = 2.0

3.0

Median = 2.5

Task 4

The class ​BST.java​ contains an implementation of a binary search tree. Write a program ​WordCount.java​ that uses this to count the number of occurrences of words read from standard input. When the input has been read the program should output each distinct word in alphabetically ascending order, along with the number of times it occurs. If the input consists of N words of which M are distinct, then the program should run in average time N lg M (and not N log N).

Example: If the input is:

99 bottles of beer on the wall, 99 bottles of beer

Then the output should be:

99 2 beer 2 bottles 2 of 2

on           1

the          1

wall,       1