implementation module BinSearchTree

import StdEnv
import BinTree


z0
        Leaf
z1
        50
        |
    ----------
    |        |
   Leaf    Leaf
z2
        50
        |
    ----------
    |        |
    10      Leaf
    |
  ------
  |    | 
 Leaf Leaf        
z3
        50
        |
    ----------
    |         |
    10        75
    |         |
  ------    ------
  |    |    |    |
 Leaf Leaf Leaf Leaf        
z4
        50
        |
    ----------
    |         |
    10        75
    |         |
  ------    ------
  |    |    |    |
 Leaf Leaf Leaf  80
                 |
               ------        
               |    |
              Leaf Leaf
z5
        50
        |
    ----------
    |         |
    10        75
    |         |
  ------    ------
  |    |    |    |
 Leaf Leaf Leaf  77
                 |
               ------
               |    |
              Leaf  80
                    |
                  ------
                  |    |
                 Leaf Leaf
z6
        50
        |
    ----------
    |         |
    10        75
    |         |
  ------    ------
  |    |    |    |
  10  Leaf Leaf  77
  |              |
 ------       ------
 |    |       |    |
Leaf Leaf    Leaf  80
                    |
                  ------
                  |    |
                 Leaf Leaf
z7
        50
        |
    ----------
    |         |
    10        75
    |         |
  ------    -----------
  |    |    |         |
  10  Leaf  75        77
  |         |         |
 ------    ------   ------
 |    |    |    |   |    |
Leaf Leaf Leaf Leaf Leaf  80
                            |
                          ------
                          |    |
                         Leaf Leaf
z8

//  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


is_geordend :: // meest algemene type
is_geordend ...

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


is_gebalanceerd :: // meest algemene type
is_gebalanceerd ...

//Start = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7]