diff options
Diffstat (limited to 'fp2/week6/mart/BinSearchTree.icl')
-rwxr-xr-x | fp2/week6/mart/BinSearchTree.icl | 49 |
1 files changed, 0 insertions, 49 deletions
diff --git a/fp2/week6/mart/BinSearchTree.icl b/fp2/week6/mart/BinSearchTree.icl deleted file mode 100755 index 83ca73b..0000000 --- a/fp2/week6/mart/BinSearchTree.icl +++ /dev/null @@ -1,49 +0,0 @@ -// 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 |