Part I: Written exercises.

1. Using the Red-Black Tree applet, you input the following numbers into the Red-Black tree, keep all red-black rules ( see the red-black rule on the bottom of the exercise ) either using color changes or rotation. The result graph should be height balance and red-black correct.

You need to follow the rules, randomly color change and rotation will result in zero credit even the result could be red-black correct.

Attach your results of screen shots for every question.

a. Insert 50, 70, 20, 90

b. Insert 50, 70, 20, 90, 99

c. Insert 50, 70, 20, 90, 80

d. Insert 50, 70, 20, 80, 60, 90, 75, 95

e. Insert 50, 70, 20, 90, 60, 55, 65, 68

Red-Black Rules

When inserting (or deleting) a new node, certain rules, which we call the red-black rules, must be followed. If they're followed, the tree will be balanced. Let's look briefly at these rules:

1. Every node is either red or black.
2. The root is always black.
3. If a node is red, its children must be black (although the converse isn't necessarily true).
4. Every path from the root to a leaf, or to a null child, must contain the same number of black nodes.

2. Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function h(x) = x %10 (table size is 10), showing the resulting

a. Separate chaining hash table
b. Open addressing hash table using linear probing.
c. Open addressing hash table using quadratic probing.
d. Open addressing hash table with second hash function h2(x) = 7- (x %7)

3. Draw the figures to show steps how to convert the binary tree to a heap using the Heapify algorithm.

4. Using the diagrams (see the attached example of heap sort) to trace the action of heapsort on the list of 1, 7, 2, 6, 3, 5, 4, give every state of your tree such as finishing a heapify or removing the root.

Part II: programming exercise

Implement the PriorityQ class using a heap instead of an array.

Attachment:- heat short.pdf