In this problem, we will consider using a binary search tree to represent a database such as the person database we considered in Problem 8 of Homework 1 and Problem 3 above. We will separate out one item of the tuples we want to represent as the key based on which we will organize the tree, and the remaining items will form the data corresponding to the key. The key is also often called the index to the data. For example, in the employee database, the key or index might be the name of the employee and the data may be a tuple consisting of the salary and the phone number. The information in the data base would then be organized into a tree structure such as the following

 (key1,data1) / \ / \ (key2,data2) (key3,data3) / \ / \ / \ / \ (key4,data4) Empty Empty (key5,data5) . . . 

In other words, the internal nodes of such trees hold the key and the data items, each internal node has a left and a right subtree and the leaves are empty trees. Of course, since this is a binary search tree, the organization is such that the keys in the left subtree at any point are smaller than the key at the node and the keys in the right subtree are larger than the key at the node; note that this property holds recursively as described.

1. Provide a type declaration that identifies a type constructor called btree that takes a pair of arguments corresponding to the type of the key and the type of the data and associated value constructors that can be used to represent trees of the form shown above. After you have provided this declaration, we should be able to write down OCaml expressions of type (ty1,ty2) btree, for suitable types ty1 and ty2, that represent trees of the kind we are interested in. Note: The OCaml type system is not strong enough to capture the ordering property for search trees, so don't spend time trying to do this. Instead, this ordering property will be an invariant of the trees we construct and manipulate through the functions we write.

2. Define an identifier called initTree that is bound to the empty binary tree (of any type) based on you representation. Specifically, your declaration should have the form

 let initTree = ... 

Note that initTree should be of type ('a,'b) btree. This is needed for automated testing: your code will be rejected by our scripts if you do not include such a definition.

3. Write down two expressions in OCaml that uses the type declarations you have provided to represent two non trivial binary search trees over different kinds of keys and data. More specifically, you should have code of the form

 let tree1 = ... let tree2 = ... 

where ... is the expression representing a relevant binary search tree. In the first tree, use an integer as the key and a string as the data. In the second tree use a string (representing a person name) as the key and a string and a real (representing a phone number and a salary) as the data. Note that we will check if the expressions you provide are of the right type by looking at their types and by determining if they satisfy the binary search tree requirement using the standard ordering on integers and strings.

4. Define a function of the following name and type

 find : ('a, 'b) btree -> 'a -> 'b option 

that takes a binary search tree and a key as input and that returns the data value stored in the tree corresponding to the key. Assume that there is exactly one entry per key in the tree. The return type has the option form in case the tree does not contain an entry corresponding to the given key. In defining this function you should obviously assume the invariant associated with binary search trees.

5. Define a function of the following name and type

 insert : ('a, 'b) btree -> 'a -> 'b -> ('a, 'b) btree 

that takes a binary search tree, a key and a data item and returns a new binary search tree that corresponds to the old tree with the given key and data item pair inserted into it. In case your experience with programming in languages such as Java or C is confusing you, note that we do not modify the old tree in OCaml but we can reuse parts of it in constructing the new tree. You should assume that the input tree satisfies the ordering invariant on binary search trees and your function is expected to preserve this invariant. One other question that often comes up: what should we do if the key already appears in the tree? The new tree should not have the old key and data association, it should have only the new one.

One important question: what ordering relation to use on the key type? In this assignment, assume that the usual, overloaded ordering relations < and > and also the equality relation = will work on this type, i.e., you can use them directly in your code. We will think of better ways of handling this aspect in future assignments, after we have talked about higher-order functions.

6. Define a function of the following name and type

 keylist : ('a, 'b) btree -> ('a list) 

that will traverse the tree and produce a list of the keys in it in the following order: first the keys in the left subtree will be listed, then the key at a node and then the keys in the right subtree. This kind of traversal is called an in-order traversal and it has the result of producing an ordered listing of the keys.

7. Define a function of the following name and type

 delete : ('a, 'b) btree -> 'a -> ('a, 'b) btree 

that takes a binary search tree and a key and returns a new binary search tree that corresponds to the old tree with a possible entry in it corresponding to the given key removed. Remember, you have to maintain the invariant for binary search trees in the process.

Note: As with all your code, we will look at the quality of your solution, so think carefully about how to organize the computation before you try to write any OCaml code for this part. This part is more difficult than the previous ones, so do not get discouraged if you are not able to solve it to your satisfaction. However, give it your best shot, this will prepare you for understanding a solution when we discuss it in class.

Hint: Since it is a slightly harder part, a suggestion may be useful. First write a function that takes a non-empty tree and produces a new tree from it that does not contain what was at the root; in my code, I called this function delete_root. Then organize the delete function so that it locates the node to be removed and uses delete_root to do this.

Your type constructor and functions must be named as we have described them here and must have the types we have indicated for them so that we can run automated tests on your program.

Language: Ocaml