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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
// Mart Lubbers, s4109503
// Camil Staps, s4498062
implementation module BinSearchTree
import StdEnv
import BinTree
z0 = Leaf
// Leaf
z1 = insertTree 50 z0
// 50
// |
// -------------
// | |
// Leaf Leaf
z2 = insertTree 10 z1
// 50
// |
// -------------
// | |
// 10 Leaf
// |
// ---------
// | |
// Leaf Leaf
z3 = insertTree 75 z2
// 50
// |
// ---------------
// | |
// 10 75
// | |
// --------- ---------
// | | | |
// Leaf Leaf Leaf Leaf
z4 = insertTree 80 z3
// 50
// |
// ---------------
// | |
// 10 75
// | |
// --------- ---------
// | | | |
// Leaf Leaf Leaf 80
// |
// ---------
// | |
// Leaf Leaf
z5 = insertTree 77 z4
// 50
// |
// ---------------
// | |
// 10 75
// | |
// --------- ---------
// | | | |
// Leaf Leaf Leaf 77
// |
// ---------
// | |
// Leaf 80
// |
// ---------
// | |
// Leaf Leaf
z6 = insertTree 10 z5
// 50
// |
// ---------------
// | |
// 10 75
// | |
// --------- ---------
// | | | |
// 10 Leaf Leaf 77
// | |
// --------- ---------
// | | | |
// Leaf Leaf Leaf 80
// |
// ---------
// | |
// Leaf Leaf
z7 = insertTree 75 z6
// 50
// |
// ----------------
// | |
// 10 75
// | |
// --------- -----------
// | | | |
// 10 Leaf 75 77
// | | |
// --------- ------ -------
// | | | | | |
// Leaf Leaf Leaf Leaf Leaf 80
// |
// ---------
// | |
// Leaf Leaf
z8 = deleteTree 50 z7
// 10
// |
// ----------------
// | |
// 10 75
// | |
// --------- -----------
// | | | |
// Leaf Leaf 75 77
// | |
// ------ -------
// | | | |
// Leaf Leaf Leaf 80
// |
// ---------
// | |
// Leaf Leaf
// 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 :: (Tree a) -> Bool | Ord a // meest algemene type
is_geordend Leaf = True
is_geordend (Node x le ri) = (foldr (&&) True (map ((>) x) (members le))) && (foldr (&&) True (map ((<=) x) (members ri))) && is_geordend le && is_geordend ri
where
members :: (Tree a) -> [a]
members Leaf = []
members (Node x le ri) = [x:(members le) ++ (members ri)]
//Start = map is_geordend [t0,t1,t2,t3,t4,t5,t6,t7]
is_gebalanceerd :: (Tree a) -> Bool | Ord a // meest algemene type
is_gebalanceerd Leaf = True
is_gebalanceerd (Node x le ri) = abs ((depth le) - (depth ri)) <= 1 && is_gebalanceerd le && is_gebalanceerd ri
where
depth :: (Tree a) -> Int
depth Leaf = 0
depth (Node x le ri) = max (depth le) (depth ri) + 1
//Start = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7]
|
