CPS 206 Fall 1999, Problem 6. Work alone.

Binary Search Trees in ML

The "btree" datatype defined below can be specialized to become a "binary search tree" (bst), by allowing the labels of each btree node to be "orderable", so that a predicate lt(a,b) can be defined on labels, where lt(a,b) is true when a "orders less than" b. The tree is then built to have the property that, for every non-leaf node (label, left, right), lt(x,label) for every x which labels a node in the btree whose root is "left", and lt(label,y) for every y which labels a node in the btree whose root is "right". If there are about as many nodes in each left and right sub-tree, such a tree can be searched quickly, to determine if a new label q is present in the tree:

datatype ('label) btree =

Empty |

Node of 'label * 'label btree * 'label btree;

fun find(q, Empty)= false |

find(q, Node( lb, left, right )) =

if lt(q, lb) then find(q, left)

else if lt(lb, q) then find(q, right)

else true;

First, define a new function add(q, t)by modifying the find(q, t) function, so it returns a new bst, with q inserted in a reasonable place if q was not present in t, and with q 's "count" incremented by 1, if q was present in t. Then write a program Count(L, k) using add(q, t) which counts the number of occurrences of each integer in a list L, and returns a list M which presents the (integer, count) pairs for the first k integers (in numeric order) encountered in L. Count must use add to build a bst (modified to accompany each integer with its count), which Count then searches to find the lowest k integers encountered in L, along with their counts.