week7/mart/BinSearchTree.icl

   1 implementation module BinSearchTree
   2
   3 import StdEnv
   4 import BinTree
   5
   6 z0 = Leaf
   7 z1 = insertTree 50 z0
   8 z2 = insertTree 10 z1
   9 z3 = insertTree 75 z2
  10 z4 = insertTree 80 z3
  11 z5 = insertTree 77 z4
  12 z6 = insertTree 10 z5
  13 z7 = insertTree 75 z6
  14 z8 = deleteTree 50 z7
  15
  16 //  Uit het diktaat, blz. 73:
  17 insertTree :: a (Tree a) -> Tree a | Ord a
  18 insertTree e Leaf = Node e Leaf Leaf
  19 insertTree e (Node x le ri)
  20 | e <= x = Node x (insertTree e le) ri
  21 | e >  x = Node x le (insertTree e ri)
  22
  23 deleteTree :: a (Tree a) -> (Tree a) | Eq, Ord a
  24 deleteTree e Leaf = Leaf
  25 deleteTree e (Node x le ri)
  26 | e <  x = Node x (deleteTree e le) ri
  27 | e == x = join le ri
  28 | e >  x = Node x le (deleteTree e ri)
  29 where
  30         join :: (Tree a) (Tree a) -> (Tree a)
  31         join Leaf b2 = b2
  32         join b1 b2 = Node x b1` b2
  33         where
  34                 (x,b1`) = largest b1
  35
  36                 largest :: (Tree a) -> (a,(Tree a))
  37                 largest (Node x b1 Leaf) = (x,b1)
  38                 largest (Node x b1 b2)   = (y,Node x b1 b2`)
  39                 where
  40                         (y,b2`) = largest b2
  41
  42
  43 is_geordend :: // meest algemene type
  44 is_geordend ...
  45
  46 Start = map is_geordend [t0,t1,t2,t3,t4,t5,t6,t7]
  47
  48
  49 is_gebalanceerd :: // meest algemene type
  50 is_gebalanceerd ...
  51
  52 //Start = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7]