Tree.lhs

	Search trees as an ADT					
                                                                      
        (c) Simon Thompson, 1995, 1998.					
                                                                                                                        
>       module Tree 
>         (Tree,
>          nil,           -- Tree a
>          isNil,         -- Tree a -> Bool  
>          isNode,        -- Tree a -> Bool
>          leftSub,       -- Tree a -> Tree a 
>          rightSub,      -- Tree a -> Tree a 
>          treeVal,       -- Tree a -> a
>          insTree,       -- Ord a => a -> Tree a -> Tree a 
>          delete,        -- Ord a => a -> Tree a -> Tree a
>          minTree        -- Ord a => Tree a -> Maybe a
>         ) where

>       data Tree a = Nil | Node a (Tree a) (Tree a)					
 

>       nil :: Tree a

>       nil = Nil

>       isNil :: Tree a -> Bool
>       isNil Nil = True
>       isNil _   = False

>       isNode :: Tree a -> Bool
>       isNode Nil = False 
>       isNode _   = True

>       leftSub, rightSub :: Tree a -> Tree a

>       leftSub Nil            = error "leftSub"
>       leftSub (Node _ t1 _) = t1

>       rightSub Nil            = error "rightSub"
>       rightSub (Node v t1 t2) = t2

>       treeVal  :: Tree a -> a

>       treeVal Nil            = error "treeVal"
>       treeVal (Node v _ _) = v

>       insTree :: Ord a => a -> Tree a -> Tree a

>       insTree val Nil = (Node val Nil Nil)

>       insTree val (Node v t1 t2)
>         | v==val 	= Node v t1 t2
>         | val > v 	= Node v t1 (insTree val t2)	
>         | val < v 	= Node v (insTree val t1) t2	

>       delete :: Ord a => a -> Tree a -> Tree a

>       delete val (Node v t1 t2)
>         | val < v 	= Node v (delete val t1) t2
>         | val > v 	= Node v t1 (delete val t2)
>         | isNil t2 	= t1
>         | isNil t1 	= t2
>         | otherwise 	= join t1 t2


>       minTree :: Ord a => Tree a -> Maybe a

>       minTree t
>         | isNil t 	= Nothing
>         | isNil t1 	= Just v
>         | otherwise 	= minTree t1
>             where
>             t1 = leftSub t
>             v  = treeVal t


The join function is an auxiliary, used in delete, where note that it
joins two trees with the property that all elements in the left are
smaller than all in the right; that will be the case for the call in
delete. 

join is not exported.

>       join :: Ord a => Tree a -> Tree a -> Tree a

>       join t1 t2 
>         = Node mini t1 newt
>           where
>           (Just mini) = minTree t2
>           newt        = delete mini t2