CSE 326 - Autumn 2000

Homework #3
Due: Friday Oct 20th

General comment on homework: whenever appropriate please show the
intermediate steps that led to your final answer.  Otherwise if the
final answer is not entirely correct we cannot help point out where
you went wrong, or provide partial credit for what you did do right.

1. Weiss 4.6.  (Provide an inductive proof, on the number of nodes in
   the tree.)

2.  Weiss 4.8.

3.  Weiss 4.19.  Note: show the intermediate tree after each operation,
or at least after every insertion and rotation pair.

4.  Suppose we implement lazy deletion in a BST by adding a field to
    the node to indicate whether it has been deleted:

	struct node { int key ; 
                      boolean deleted ; 
                      node * left; 
                      node * right }

    (a) Provide pseudocode for the routine

	node * findMin( node * root )

        that returns a pointer to the node containing the smallest
        non-deleted value in the BST.  (The guidelines for pseudocode
        from the previous homework are now on the course web page.)
        When called on a tree containing no deleted nodes at all, your
        routine should be as efficient as the version of findMin discussed
        in class.

    (b) Suppose the BST contains n nodes and has depth log(n).  Some
	number of the nodes have been marked as deleted.  What
	is the *worst-case* asymptotic running time (theta) for
	findMin?  Give an example of when the worst case might occur.

    (c) What other information would it be useful to store at every
        node in the tree in order to improve this worst case running
        time?  (It should be possible to keep this information current
        without making the asymptotic complexity of the other operations
        operations -- insert, find, and delete -- worse.)
        If the tree again contains n nodes and has depth
        log(n), what is the O() bound on the worst-case running time
        for a version of findMin that takes advantage of this
        information?