0.9 Exercises  (Page 3/5)

Exercises 5.15

Give a recursive version of the TREE-INSERT procedure.

Exercises 5.16

Suppose that a binary search tree is constructed by repeatedly inserting distinct values into the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted into the tree.

Exercises 5.17

We can sort a given set of n numbers by first building a binary search tree containing these numbers (using TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm?

Exercises 5.18

Suppose that another data structure contains a pointer to a node y in a binary search tree, and suppose that y's predecessor z is deleted from the tree by the procedure TREE-DELETE. What problem can arise? How can TREE-DELETE be rewritten to solve this problem?

Exercises 5.19

Is the operation of deletion "commutative" in the sense that deleting x and then y from a

binary search tree leaves the same tree as deleting y and then x? Argue why it is or give a counterexample.

Exercises 5.20

When node z in TREE-DELETE has two children, we could splice out its predecessor rather than its successor. Some have argued that a fair strategy, giving equal priority to predecessor and successor, yields better empirical performance. How might TREE-DELETE be changed to implement such a fair strategy?

Chapter 6. sorting

Exercises 6.1

What are the minimum and maximum numbers of elements in a heap of height h?

Exercises 6.2

Show that in any subtree of a max-heap, the root of the subtree contains the largest value

occurring anywhere in that subtree.

Exercises 6.3

Where in a max-heap might the smallest element reside, assuming that all elements are

distinct?

Exercises 6.4

Is an array that is in sorted order a min-heap?

Exercises 6.5

Is the sequence _23, 17, 14, 6, 13, 10, 1, 5, 7, 12_ a max-heap?

Exercises 6.6

Using Figure above as a model, illustrate the operation of MAX-HEAPIFY(A, 3) on the array A = _27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0_.

Exercises 6.7

Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MINHEAPIFY( A, i), which performs the corresponding manipulation on a min-heap. How does the running time of MIN-HEAPIFY compare to that of MAX-HEAPIFY?

Exercises 6.8

What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?

Exercises 6.9

What is the effect of calling MAX-HEAPIFY(A, i) for i>heap-size[A]/2?

Exercises 6.10

The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an iterative control construct (a loop) instead of recursion.

Exercises 6.11

Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is Ω(lg n).

(Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called