1 implementation module BinSearchTree
34 // --------- ---------
36 // Leaf Leaf Leaf Leaf
45 // --------- ---------
60 // --------- ---------
79 // --------- ---------
83 // --------- ---------
98 // --------- -----------
102 // --------- ------ -------
104 // Leaf Leaf Leaf Leaf Leaf 80
110 z8 = deleteTree 50 z7
117 // --------- -----------
129 // Uit het diktaat, blz. 73:
130 insertTree :: a (Tree a) -> Tree a | Ord a
131 insertTree e Leaf = Node e Leaf Leaf
132 insertTree e (Node x le ri)
133 | e <= x = Node x (insertTree e le) ri
134 | e > x = Node x le (insertTree e ri)
136 deleteTree :: a (Tree a) -> (Tree a) | Eq, Ord a
137 deleteTree e Leaf = Leaf
138 deleteTree e (Node x le ri)
139 | e < x = Node x (deleteTree e le) ri
140 | e == x = join le ri
141 | e > x = Node x le (deleteTree e ri)
143 join :: (Tree a) (Tree a) -> (Tree a)
145 join b1 b2 = Node x b1` b2
149 largest :: (Tree a) -> (a,(Tree a))
150 largest (Node x b1 Leaf) = (x,b1)
151 largest (Node x b1 b2) = (y,Node x b1 b2`)
156 is_geordend :: (Tree a) -> Bool | Ord a // meest algemene type
157 is_geordend Leaf = True
158 is_geordend (Node x le ri) = (foldr (&&) True (map ((>) x) (members le))) && (foldr (&&) True (map ((<=) x) (members ri))) && is_geordend le && is_geordend ri
160 members :: (Tree a) -> [a]
162 members (Node x le ri) = [x:(members le) ++ (members ri)]
164 //Start = map is_geordend [t0,t1,t2,t3,t4,t5,t6,t7]
166 is_gebalanceerd :: (Tree a) -> Bool | Ord a // meest algemene type
167 is_gebalanceerd Leaf = True
168 is_gebalanceerd (Node x le ri) = abs ((depth le) - (depth ri)) <= 1 && is_gebalanceerd le && is_gebalanceerd ri
170 depth :: (Tree a) -> Int
172 depth (Node x le ri) = max (depth le) (depth ri) + 1
174 //Start = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7]