1 // Mart Lubbers, s4109503
2 // Camil Staps, s4498062
4 implementation module BinSearchTree
37 // --------- ---------
39 // Leaf Leaf Leaf Leaf
48 // --------- ---------
63 // --------- ---------
82 // --------- ---------
86 // --------- ---------
101 // --------- -----------
105 // --------- ------ -------
107 // Leaf Leaf Leaf Leaf Leaf 80
113 z8 = deleteTree 50 z7
120 // --------- -----------
132 // Uit het diktaat, blz. 73:
133 insertTree :: a (Tree a) -> Tree a | Ord a
134 insertTree e Leaf = Node e Leaf Leaf
135 insertTree e (Node x le ri)
136 | e <= x = Node x (insertTree e le) ri
137 | e > x = Node x le (insertTree e ri)
139 deleteTree :: a (Tree a) -> (Tree a) | Eq, Ord a
140 deleteTree e Leaf = Leaf
141 deleteTree e (Node x le ri)
142 | e < x = Node x (deleteTree e le) ri
143 | e == x = join le ri
144 | e > x = Node x le (deleteTree e ri)
146 join :: (Tree a) (Tree a) -> (Tree a)
148 join b1 b2 = Node x b1` b2
152 largest :: (Tree a) -> (a,(Tree a))
153 largest (Node x b1 Leaf) = (x,b1)
154 largest (Node x b1 b2) = (y,Node x b1 b2`)
159 is_geordend :: (Tree a) -> Bool | Ord a // meest algemene type
160 is_geordend Leaf = True
161 is_geordend (Node x le ri) = (foldr (&&) True (map ((>) x) (members le))) && (foldr (&&) True (map ((<=) x) (members ri))) && is_geordend le && is_geordend ri
163 members :: (Tree a) -> [a]
165 members (Node x le ri) = [x:(members le) ++ (members ri)]
167 //Start = map is_geordend [t0,t1,t2,t3,t4,t5,t6,t7]
169 is_gebalanceerd :: (Tree a) -> Bool | Ord a // meest algemene type
170 is_gebalanceerd Leaf = True
171 is_gebalanceerd (Node x le ri) = abs ((depth le) - (depth ri)) <= 1 && is_gebalanceerd le && is_gebalanceerd ri
173 depth :: (Tree a) -> Int
175 depth (Node x le ri) = max (depth le) (depth ri) + 1
177 //Start = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7]