module Tree(
	Tree,
	nil,
	isNil,
	isNode,
	leftSub,
	rightSub,
	treeVal,
	insTree,
	remove,
	minTree,
	binSearch,
	test
	)where



data Tree a b  = Nil | Node (a,b)  (Tree  a b ) (Tree a b )
	deriving Show

nil :: Tree a b
nil = Nil


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



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

leftSub,rightSub :: Tree a b->Tree a b
leftSub Nil = error "leftSub"
leftSub (Node _ t1 _) = t1

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

treeVal :: Tree a b->(a,b)
treeVal Nil = error "treeVal"
treeVal (Node v _ _) = v

insTree :: Ord a=>(a,b)->Tree a b->Tree a b
insTree (na,nb) Nil = (Node (na,nb) Nil Nil)
insTree (na,nb) (Node (va,vb) t1 t2)
	|na == va = Node (va,vb) t1 t2
	|na > va = Node (va,vb) t1 (insTree (na,nb) t2)
	|na < va = Node (va,vb) (insTree (na,nb) t1) t2


remove :: Ord a=>a->Tree a b->Tree a b
remove na (Node (va,vb) t1 t2)
	|na < va = Node (va,vb) (remove na t1) t2
	|na > va = Node (va,vb) t1 (remove na t2)
	|isNil t2 = t1
	|isNil t1 = t2
	|otherwise = join t1 t2


minTree :: Ord a=>Tree a b->Maybe (a,b)
minTree t
	|isNil t = Nothing
	|isNil t1 = Just v
	|otherwise = minTree t1
		where
		t1 = leftSub t
		v = treeVal t

join :: Ord a=>Tree a b->Tree a b->Tree a b
join t1 t2
	=Node mini t1 newt
		where
		(Just mini) = minTree t2
		newt = remove (fst mini) t2


binSearch :: Ord a =>Tree a b->a->Maybe b
binSearch Nil na = Nothing
binSearch (Node (va,vb) t1 t2) na
	|na == va = Just vb
	|na < va = binSearch t1 na
	|na > va = binSearch t2 na


test :: Tree [Char] Int
test = Node ("wu",33) (Node ("he",22) Nil Nil) (Node ("xiao",11) Nil Nil)