fp2/week6/mart/BinSearchTree.icl

   1 // Mart Lubbers, s4109503
   2 // Camil Staps, s4498062
   3
   4 implementation module BinSearchTree
   5
   6 import StdEnv
   7 import BinTree
   8
   9 insertTree :: a (BTree a) -> BTree a | Ord a
  10 insertTree e BLeaf = BNode e BLeaf BLeaf
  11 insertTree e (BNode x le ri)
  12 | e <= x = BNode x (insertTree e le) ri
  13 | e >  x = BNode x le (insertTree e ri)
  14
  15 deleteTree :: a (BTree a) -> (BTree a) | Eq, Ord a
  16 deleteTree e BLeaf = BLeaf
  17 deleteTree e (BNode x le ri)
  18 | e <  x = BNode x (deleteTree e le) ri
  19 | e == x = join le ri
  20 | e >  x = BNode x le (deleteTree e ri)
  21 where
  22     join :: (BTree a) (BTree a) -> (BTree a)
  23     join BLeaf b2 = b2
  24     join b1 b2 = BNode x b1` b2
  25     where
  26         (x,b1`) = largest b1
  27
  28         largest :: (BTree a) -> (a,(BTree a))
  29         largest (BNode x b1 BLeaf) = (x,b1)
  30         largest (BNode x b1 b2)   = (y,BNode x b1 b2`)
  31         where
  32             (y,b2`) = largest b2
  33
  34
  35 is_geordend :: (BTree a) -> Bool | Ord a // meest algemene type
  36 is_geordend BLeaf = True
  37 is_geordend (BNode x le ri) = (foldr (&&) True (map ((>) x) (members le))) && (foldr (&&) True (map ((<=) x) (members ri))) && is_geordend le && is_geordend ri
  38 where
  39     members :: (BTree a) -> [a]
  40     members BLeaf = []
  41     members (BNode x le ri) = [x:(members le) ++ (members ri)]
  42
  43 is_gebalanceerd :: (BTree a) -> Bool | Ord a // meest algemene type
  44 is_gebalanceerd BLeaf = True
  45 is_gebalanceerd (BNode x le ri) = abs ((depth le) - (depth ri)) <= 1 && is_gebalanceerd le && is_gebalanceerd ri
  46 where
  47     depth :: (BTree a) -> Int
  48     depth BLeaf = 0
  49     depth (BNode x le ri) = max (depth le) (depth ri) + 1