T÷lvunarfrŠ­i 2

Weekly note 14

This is the last week in which we will cover new material. There is only a lecture on the tuesday, as the thursday April 21st is the first day of summer, which is a teaching holiday. On the tuesday we will therefore finish up with binary search trees from Chapter 12.

Next week there will only be section where we will go over the exercises below. Also, on the tuesday April 26 at 11:05 there will be an overview of the course material, explanation of the structure of the exam, and students can ask question on the material.

Problem set 11

Solve the following problems and put the solutions into your section teacher's box before noon monday April 25th. They will not accept solutions that arrive later.

  1. Exercise 12.47 on page 521 in the textbook.

  2. What order of the input keys E, A, S, Y, Q, U, E, S, T, I, O, N will result in a binary search tree with the lowest possible height? Assume that the insertion uses Program 12.8 on page 517 in the textbook.

  3. Show a recursive definition of the function getmin( T ) on a binary search tree. The function returns the smallest key in the tree T. The definition should be in the same spirit at the definitions in section 2 of Anna's handout. You can use a more graphic notation as was used in the lectures.

  4. Show the tree below after node 15 has been lifted up above node 10 (i.e. left rotation at 10):
                                    /   \
                                   3    10
                                  /    /   \
                                 1    8    15
                                          /   \
                                         12   20

  5. [Makeup exam 2004] All the items of a heap are to be to put into a binary search tree. The heap is given as an N-item array and you can only use the operation insert on the binary search tree. i) Would it be sensible to insert the items in the order that they appear in the array, i.e. first pq[1], then pq[2], etc.? ii) How about the reverse order (i.e. start with pq[N])? iii) Is there any other insertion order of items from the heap array that would be better than the two methods mentioned above? Justify all your answers.

annaing (hja) hi.is / hh (hja) hi.is, April 18th, 2005.