implementation module BinSearchTree

import StdEnv
import BinTree
import BinTreePrint
//(Node :: a (Tree a) (Tree a) -> (Tree a)
// Leaf is a data constructor of arity zero (Leaf :: Tree a)
z0 = Leaf
z1 = insertTree 50 z0
z2 = insertTree 10 z1
z3 = insertTree 75 z2
z4 = insertTree 80 z3
z5 = insertTree 77 z4
z6 = insertTree 10 z5
z7 = insertTree 75 z6
z8 = deleteTree 50 z7

Start0 = toString z7
Start1 = toString z8
Start2 = toString t7

//  Uit het diktaat, blz. 73:
insertTree :: a (Tree a) -> Tree a | Ord a
insertTree e Leaf = Node e Leaf Leaf
insertTree e (Node x le ri)
| e <= x = Node x (insertTree e le) ri
| e >  x = Node x le (insertTree e ri)

deleteTree :: a (Tree a) -> (Tree a) | Eq, Ord a
deleteTree e Leaf = Leaf
deleteTree e (Node x le ri)
| e <  x = Node x (deleteTree e le) ri
| e == x = join le ri
| e >  x = Node x le (deleteTree e ri)
where
	join :: (Tree a) (Tree a) -> (Tree a)
	join Leaf b2 = b2
	join b1 b2 = Node x b1` b2
	where
		(x,b1`) = largest b1

		largest :: (Tree a) -> (a,(Tree a))
		largest (Node x b1 Leaf) = (x,b1)
		largest (Node x b1 b2)   = (y,Node x b1 b2`)
		where
			(y,b2`) = largest b2

full_tree_check :: (a a -> Bool) a (Tree a) -> Bool | Ord a
full_tree_check _ _ Leaf = True
full_tree_check f x (Node n l r)
|f n x = (full_tree_check f x l) && (full_tree_check f x r)
|otherwise = False

is_geordend :: (Tree a) -> Bool | Ord a
is_geordend Leaf = True
is_geordend (Node x  Leaf Leaf) = True
is_geordend (Node x Leaf ri)
|  full_tree_check (>=) x ri = is_geordend ri
| otherwise = False
is_geordend (Node x le Leaf)
|  full_tree_check (<=) x le = is_geordend le
| otherwise = False
is_geordend (Node x le ri)
|  (full_tree_check (<=) x le) && (full_tree_check (>=) x ri)= is_geordend le && is_geordend ri
|  otherwise = False


Start3 = map is_geordend [t0,t1,t2,t3,t4,t5,t6,t7]


is_gebalanceerd :: (Tree a) -> Bool
is_gebalanceerd Leaf = True
is_gebalanceerd (Node _ l r)
| (d <= 1) && (d >= -1) = True
| otherwise = False where d = (diepte l) - (diepte r)

Start4 = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7]
Start = (
		//Start0,'\n',
		//Start1,'\n',
		Start2,'\n',
		Start3,'\n',
		Start4,'\n'
		)