1 // Mart Lubbers, s4109503
2 // Camil Staps, s4498062
4 implementation module BinSearchTree
9 insertTree :: a (BTree a) -> BTree a | Ord a
10 insertTree e BLeaf = BNode e BLeaf BLeaf
11 insertTree e (BNode x le ri)
12 | e <= x = BNode x (insertTree e le) ri
13 | e > x = BNode x le (insertTree e ri)
15 deleteTree :: a (BTree a) -> (BTree a) | Eq, Ord a
16 deleteTree e BLeaf = BLeaf
17 deleteTree e (BNode x le ri)
18 | e < x = BNode x (deleteTree e le) ri
20 | e > x = BNode x le (deleteTree e ri)
22 join :: (BTree a) (BTree a) -> (BTree a)
24 join b1 b2 = BNode x b1` b2
28 largest :: (BTree a) -> (a,(BTree a))
29 largest (BNode x b1 BLeaf) = (x,b1)
30 largest (BNode x b1 b2) = (y,BNode x b1 b2`)
35 is_geordend :: (BTree a) -> Bool | Ord a // meest algemene type
36 is_geordend BLeaf = True
37 is_geordend (BNode x le ri) = (foldr (&&) True (map ((>) x) (members le))) && (foldr (&&) True (map ((<=) x) (members ri))) && is_geordend le && is_geordend ri
39 members :: (BTree a) -> [a]
41 members (BNode x le ri) = [x:(members le) ++ (members ri)]
43 is_gebalanceerd :: (BTree a) -> Bool | Ord a // meest algemene type
44 is_gebalanceerd BLeaf = True
45 is_gebalanceerd (BNode x le ri) = abs ((depth le) - (depth ri)) <= 1 && is_gebalanceerd le && is_gebalanceerd ri
47 depth :: (BTree a) -> Int
49 depth (BNode x le ri) = max (depth le) (depth ri) + 1