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]
