CIS-610 Data Structures and Algorithms

Home Work #8							Due:	11/04/1999


1. Modify the search and insertion algorithm to become update algorithms. If an algorithm finds a j such that key equals k(j) , change the value of r(j) to rec.

2. Write an efficient insertion algorithm for a binary search tree to insert a new record whose key is known not to exist in the tree.

3. Write an algorithm to delete a node from a binary tree that replaces the node with its inorder predecessor, rather than its inorder successor.

4. Suppose that the node type of a binary search tree is defined as follows:

Struct nodetype {
	Int k;
	Int r;
	Struct nodetype *left;
	Struct nodetype *right;
};

The k and r fields contain the key and record of the node; left and right are pointers to the node's sons. Write a routine sinsert(tree, key, rec) to search and insert a record rec with key key into a binary search tree pointed to by tree.

5. Write a routine sdelete( tree, key1, key2) to delete all records with keys between key1 and key2 (inclusively) from a binary search tree whose nodes are declared as in the previous exercise.

6. Choose any large paragraph from a book. Insert each word of the paragraph, in order, into an initially empty top-down multiway search tree of order 5, omitting any duplication.