diff options
| author | Camil Staps | 2016-02-02 19:24:50 +0100 |
|---|---|---|
| committer | Camil Staps | 2016-02-02 19:24:50 +0100 |
| commit | a7d7542dc646a5fd124ef71e71ce260889f1701b (patch) | |
| tree | 04ed89503bbb3cc9933273a1326a53ca724c3492 /fp1/week7/camil/BinSearchTree.icl | |
| parent | week6 camil: working positioning of lines by putting empties at left and righ... (diff) | |
Diffstat (limited to 'fp1/week7/camil/BinSearchTree.icl')
| -rw-r--r-- | fp1/week7/camil/BinSearchTree.icl | 177 |
1 files changed, 0 insertions, 177 deletions
diff --git a/fp1/week7/camil/BinSearchTree.icl b/fp1/week7/camil/BinSearchTree.icl deleted file mode 100644 index 559846b..0000000 --- a/fp1/week7/camil/BinSearchTree.icl +++ /dev/null @@ -1,177 +0,0 @@ -// Mart Lubbers, s4109503 -// Camil Staps, s4498062 - -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] |