8.3 camil

diff --git a/week7/camil/BinSearchTree.dcl b/week7/camil/BinSearchTree.dcl
new file mode 100644 (file)
index 0000000..696b065
--- /dev/null
+++ b/week7/camil/BinSearchTree.dcl
@@ -0,0 +1,7 @@
+definition module BinSearchTree\r
+\r
+import StdClass\r
+import BinTree\r
+\r
+is_geordend     :: (Tree a) -> Bool | Ord a // meest algemene type\r
+is_gebalanceerd :: (Tree a) -> Bool | Ord a // meest algemene type\r

diff --git a/week7/camil/BinSearchTree.icl b/week7/camil/BinSearchTree.icl
new file mode 100644 (file)
index 0000000..b50a605
--- /dev/null
+++ b/week7/camil/BinSearchTree.icl
@@ -0,0 +1,174 @@
+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]

diff --git a/week7/camil/BinTree.dcl b/week7/camil/BinTree.dcl
new file mode 100644 (file)
index 0000000..7774ece
--- /dev/null
+++ b/week7/camil/BinTree.dcl
@@ -0,0 +1,16 @@
+definition module BinTree\r
+\r
+::  Tree a = Node a (Tree a) (Tree a) | Leaf\r
+\r
+t0 :: Tree Int\r
+t1 :: Tree Int\r
+t2 :: Tree Int\r
+t3 :: Tree Int\r
+t4 :: Tree Int\r
+t5 :: Tree Int\r
+t6 :: Tree Int\r
+t7 :: Tree Int\r
+\r
+//nodes  :: // meest algemene type\r
+//leaves :: // meest algemene type\r
+//diepte :: // meest algemene type\r

diff --git a/week7/camil/BinTree.icl b/week7/camil/BinTree.icl
new file mode 100644 (file)
index 0000000..601efcc
--- /dev/null
+++ b/week7/camil/BinTree.icl
@@ -0,0 +1,38 @@
+implementation module BinTree\r
+\r
+import StdEnv\r
+\r
+::  Tree a = Node a (Tree a) (Tree a) | Leaf\r
+\r
+t0 :: Tree Int\r
+t0 = Leaf\r
+t1 :: Tree Int\r
+t1 = Node 4 t0 t0\r
+t2 :: Tree Int\r
+t2 = Node 2 t0 t1\r
+t3 :: Tree Int\r
+t3 = Node 5 t2 t0\r
+t4 :: Tree Int\r
+t4 = Node 5 t2 t2\r
+t5 :: Tree Int\r
+t5 = Node 1 Leaf (Node 2 Leaf (Node 3 Leaf (Node 4 Leaf Leaf)))\r
+t6 :: Tree Int\r
+t6 = Node 1 (Node 2 (Node 3 (Node 4 Leaf Leaf) Leaf) Leaf) Leaf\r
+t7 :: Tree Int\r
+t7 = Node 4 (Node 1 Leaf Leaf) (Node 5 (Node 2 Leaf Leaf) Leaf)\r
+\r
+//  2.\r
+//nodes :: // meest algemene type\r
+//nodes ...\r
+\r
+//Start = map nodes [t0,t1,t2,t3,t4,t5,t6,t7]\r
+\r
+//leaves :: // meest algemene type\r
+//leaves ...\r
+\r
+//Start = map leaves [t0,t1,t2,t3,t4,t5,t6,t7]\r
+\r
+//diepte :: // meest algemene type\r
+//diepte ...\r
+\r
+//Start = map diepte [t0,t1,t2,t3,t4,t5,t6,t7]\r