Introduction to Programming

Assignment 7

Date: Wed, 10 November 2004

Due on: Fri, 19 November 2004

Balanced search trees

Write a module BalancedSearchTree that implements balanced binary search trees. Use the name "BStree a" to denote the datatype. Your implementation should support the following functions.

1.     find :: (BStree a) -> a -> Bool
       -- Reports whether the given value is found in the tree
       

2.     insert :: (BStree a) -> a -> (BStree a)    
       -- Inserts a value into the tree, maintaining logarithmic
       -- height
       

3.     delete :: (BStree a) -> a -> (BStree a)    
       -- Deletes a value from the tree, maintaining logarithmic
       -- height
       

4.     height :: (BStree a) -> Int
       -- Returns the height of the tree
       

5.     size :: (BStree a) -> Init
       -- Returns the number of nodes in the tree
       

6.     isemptytree :: (BStree a) -> Bool
       -- Tells whether the tree is empty
       

7.     emptytree :: (BStree a)
       -- Returns an empty tree
       

8.     buildtree :: [a] -> (BStree a)
       -- Build a search tree in linear time from a sorted list
       

9.     listtree :: (BStree a) -> [a]
       -- List out the values in the tree in ascending order, in
       -- linear time