blob: 83ca73b7f6d7ecac8ebeb22f5b933edacaba5d3e (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
// Mart Lubbers, s4109503
// Camil Staps, s4498062
implementation module BinSearchTree
import StdEnv
import BinTree
insertTree :: a (BTree a) -> BTree a | Ord a
insertTree e BLeaf = BNode e BLeaf BLeaf
insertTree e (BNode x le ri)
| e <= x = BNode x (insertTree e le) ri
| e > x = BNode x le (insertTree e ri)
deleteTree :: a (BTree a) -> (BTree a) | Eq, Ord a
deleteTree e BLeaf = BLeaf
deleteTree e (BNode x le ri)
| e < x = BNode x (deleteTree e le) ri
| e == x = join le ri
| e > x = BNode x le (deleteTree e ri)
where
join :: (BTree a) (BTree a) -> (BTree a)
join BLeaf b2 = b2
join b1 b2 = BNode x b1` b2
where
(x,b1`) = largest b1
largest :: (BTree a) -> (a,(BTree a))
largest (BNode x b1 BLeaf) = (x,b1)
largest (BNode x b1 b2) = (y,BNode x b1 b2`)
where
(y,b2`) = largest b2
is_geordend :: (BTree a) -> Bool | Ord a // meest algemene type
is_geordend BLeaf = True
is_geordend (BNode x le ri) = (foldr (&&) True (map ((>) x) (members le))) && (foldr (&&) True (map ((<=) x) (members ri))) && is_geordend le && is_geordend ri
where
members :: (BTree a) -> [a]
members BLeaf = []
members (BNode x le ri) = [x:(members le) ++ (members ri)]
is_gebalanceerd :: (BTree a) -> Bool | Ord a // meest algemene type
is_gebalanceerd BLeaf = True
is_gebalanceerd (BNode x le ri) = abs ((depth le) - (depth ri)) <= 1 && is_gebalanceerd le && is_gebalanceerd ri
where
depth :: (BTree a) -> Int
depth BLeaf = 0
depth (BNode x le ri) = max (depth le) (depth ri) + 1
|
