hoi

[fp1415.git] / fp2 / week6 / mart / BinSearchTree.icl

diff --git a/fp2/week6/mart/BinSearchTree.icl b/fp2/week6/mart/BinSearchTree.icl
new file mode 100755 (executable)
index 0000000..83ca73b
--- /dev/null
+++ b/fp2/week6/mart/BinSearchTree.icl
@@ -0,0 +1,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
\ No newline at end of file