1. Trees

(a) (4) Find a tree diagram, above, that is NOT a binary search tree. Explain why it is not.

(b) (4) Trees 2 and 3 look something like min-heap. One is, one is not. Which one is not?

Explainwhy.

(c) (4) Is tree 4, above, balanced? If not, why not? If so, add one node to make it unbalanced.

(d) (4) Write down the values of the nodes in tree 3, in the order that a breadth-first search

wouldvisit them.

(e) (4) If you start with a binary search tree with 30 elements in it, and delete the minimum

element10 times, the resulting tree will have a bad property. Explain what this property is and

why it will occur.

2. Red-Black Trees

(4) Start with the red-black tree on the right. The root is black, and 21 and 88 are both red. Insert a node

containing 30 and show how the tree changes. Be very clear about the colors of the four nodes at the end of the

process.

(a) (4) After inserting the 30, how many more nodes can

youinsert in this tree without causing a re-balancing

operation? What nodes would you insert?

(b) (4) After inserting the 30, is it possible to force a rebalancing

by adding just one more node? If so, where?

(c) (4) Explain why, in general, an AVL tree or a Red-Black treegives better performance

than a binary search tree.

3. Heaps

The diagram below is a min-heap of integers. Starting with this heap, make the changes below, in

order, using the result from the prior change. Redraw the heap as you work out each change.

Figure 1:

(a) (4) Insert the number 13 into this heap.

(b) (6) Delete the top item on the heap and readjust the rest according to the deletion algorithm.

4. Quicksort.

tree 1

tree 2 tree 3 2

8

11 12

6

5

37

3

17

2

8

11 12

6

5

37

3

2 17

8

11

12

6

5

37

3

17

tree 4

2

8

11

6 12

5

37

3

17

2 4 3 5 6 3 8 29 14 25 19 32 61 21 16 30 38 15

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

21 88

45

These questions apply to the version of quicksort that was discussed in class. In that program, two

functions implement the heart of the quicksort algorithm:

void quick(int first, int last);// recursive int partition( int first, int last ); // a

nested loop

(a) (3) The first step in the partition process is to select a pivot element and move it into position.

Do that for the array below. In the space given, rewrite the array with the pivot in place.

Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Before: 68 38 91 30 74 25 97 63 23 25 71 49 35 40 29 41

w.Pivot:___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___

(b) (6) Using the array with the pivot element in place, simulate one pass of the partition() function

when called thus: split = partition(0, 15). Copy the data onto the blank line below as the

scanners pass over it, showing each swap that takes place. Show the final swap that involves

the pivot.

Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

After: ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___

(c) (2) What integer result will be returned by partition and stored in split?

(d) (4) What will the arguments be for the two recursive calls on quick()?

5. Expressions

(a) (4) Start with the parse tee on the right. Do a prefixtreewalkon this tree and write down the resulting prefix

expression.

(b) (4) Now do a postfix treewalk and write down the

resultingpostfix expression.

(c) (4) This parse tree is the result of performing a

precedenceparse on an ordinary C arithmetic expression.

What is that expression? Remember, infix expressions

sometimes need parentheses.

y

+

x 2 3

*

=

https://customwriting.s3.amazonaws.com/GH347/eedsaa.pdf?versionId=vVKYsqGWHvbFU5siWhporAqh_gTGlRVU&AWSAccessKeyId=AKIAIDY3BOXYKEAMAEOQ&Expires=1462292948&Signature=FaQF4SSgmJ1R9hNPqicreU%2BW0zs%3D

**TAKE ADVANTAGE OF OUR PROMOTIONAL DISCOUNT DISPLAYED ON THE WEBSITE AND GET A DISCOUNT FOR YOUR PAPER NOW!**