diff options
| -rw-r--r-- | week7/camil/BinSearchTree.dcl | 7 | ||||
| -rw-r--r-- | week7/camil/BinSearchTree.icl | 174 | ||||
| -rw-r--r-- | week7/camil/BinTree.dcl | 16 | ||||
| -rw-r--r-- | week7/camil/BinTree.icl | 38 |
4 files changed, 235 insertions, 0 deletions
diff --git a/week7/camil/BinSearchTree.dcl b/week7/camil/BinSearchTree.dcl new file mode 100644 index 0000000..696b065 --- /dev/null +++ b/week7/camil/BinSearchTree.dcl @@ -0,0 +1,7 @@ +definition module BinSearchTree
+
+import StdClass
+import BinTree
+
+is_geordend :: (Tree a) -> Bool | Ord a // meest algemene type
+is_gebalanceerd :: (Tree a) -> Bool | Ord a // meest algemene type
diff --git a/week7/camil/BinSearchTree.icl b/week7/camil/BinSearchTree.icl new file mode 100644 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 index 0000000..7774ece --- /dev/null +++ b/week7/camil/BinTree.dcl @@ -0,0 +1,16 @@ +definition module BinTree
+
+:: Tree a = Node a (Tree a) (Tree a) | Leaf
+
+t0 :: Tree Int
+t1 :: Tree Int
+t2 :: Tree Int
+t3 :: Tree Int
+t4 :: Tree Int
+t5 :: Tree Int
+t6 :: Tree Int
+t7 :: Tree Int
+
+//nodes :: // meest algemene type
+//leaves :: // meest algemene type
+//diepte :: // meest algemene type
diff --git a/week7/camil/BinTree.icl b/week7/camil/BinTree.icl new file mode 100644 index 0000000..601efcc --- /dev/null +++ b/week7/camil/BinTree.icl @@ -0,0 +1,38 @@ +implementation module BinTree
+
+import StdEnv
+
+:: Tree a = Node a (Tree a) (Tree a) | Leaf
+
+t0 :: Tree Int
+t0 = Leaf
+t1 :: Tree Int
+t1 = Node 4 t0 t0
+t2 :: Tree Int
+t2 = Node 2 t0 t1
+t3 :: Tree Int
+t3 = Node 5 t2 t0
+t4 :: Tree Int
+t4 = Node 5 t2 t2
+t5 :: Tree Int
+t5 = Node 1 Leaf (Node 2 Leaf (Node 3 Leaf (Node 4 Leaf Leaf)))
+t6 :: Tree Int
+t6 = Node 1 (Node 2 (Node 3 (Node 4 Leaf Leaf) Leaf) Leaf) Leaf
+t7 :: Tree Int
+t7 = Node 4 (Node 1 Leaf Leaf) (Node 5 (Node 2 Leaf Leaf) Leaf)
+
+// 2.
+//nodes :: // meest algemene type
+//nodes ...
+
+//Start = map nodes [t0,t1,t2,t3,t4,t5,t6,t7]
+
+//leaves :: // meest algemene type
+//leaves ...
+
+//Start = map leaves [t0,t1,t2,t3,t4,t5,t6,t7]
+
+//diepte :: // meest algemene type
+//diepte ...
+
+//Start = map diepte [t0,t1,t2,t3,t4,t5,t6,t7]
|