week7/mart/BinSearchTree.icl

   1 implementation module BinSearchTree
   2
   3 import StdEnv
   4 import BinTree
   5
   6
   7 z0
   8         Leaf
   9 z1
  10         50
  11         |
  12     ----------
  13     |        |
  14    Leaf    Leaf
  15 z2
  16         50
  17         |
  18     ----------
  19     |        |
  20     10      Leaf
  21     |
  22   ------
  23   |    |
  24  Leaf Leaf
  25 z3
  26         50
  27         |
  28     ----------
  29     |         |
  30     10        75
  31     |         |
  32   ------    ------
  33   |    |    |    |
  34  Leaf Leaf Leaf Leaf
  35 z4
  36         50
  37         |
  38     ----------
  39     |         |
  40     10        75
  41     |         |
  42   ------    ------
  43   |    |    |    |
  44  Leaf Leaf Leaf  80
  45                  |
  46                ------
  47                |    |
  48               Leaf Leaf
  49 z5
  50         50
  51         |
  52     ----------
  53     |         |
  54     10        75
  55     |         |
  56   ------    ------
  57   |    |    |    |
  58  Leaf Leaf Leaf  77
  59                  |
  60                ------
  61                |    |
  62               Leaf  80
  63                     |
  64                   ------
  65                   |    |
  66                  Leaf Leaf
  67 z6
  68         50
  69         |
  70     ----------
  71     |         |
  72     10        75
  73     |         |
  74   ------    ------
  75   |    |    |    |
  76   10  Leaf Leaf  77
  77   |              |
  78  ------       ------
  79  |    |       |    |
  80 Leaf Leaf    Leaf  80
  81                     |
  82                   ------
  83                   |    |
  84                  Leaf Leaf
  85 z7
  86         50
  87         |
  88     ----------
  89     |         |
  90     10        75
  91     |         |
  92   ------    -----------
  93   |    |    |         |
  94   10  Leaf  75        77
  95   |         |         |
  96  ------    ------   ------
  97  |    |    |    |   |    |
  98 Leaf Leaf Leaf Leaf Leaf  80
  99                             |
 100                           ------
 101                           |    |
 102                          Leaf Leaf
 103 z8
 104
 105 //  Uit het diktaat, blz. 73:
 106 insertTree :: a (Tree a) -> Tree a | Ord a
 107 insertTree e Leaf = Node e Leaf Leaf
 108 insertTree e (Node x le ri)
 109 | e <= x = Node x (insertTree e le) ri
 110 | e >  x = Node x le (insertTree e ri)
 111
 112 deleteTree :: a (Tree a) -> (Tree a) | Eq, Ord a
 113 deleteTree e Leaf = Leaf
 114 deleteTree e (Node x le ri)
 115 | e <  x = Node x (deleteTree e le) ri
 116 | e == x = join le ri
 117 | e >  x = Node x le (deleteTree e ri)
 118 where
 119         join :: (Tree a) (Tree a) -> (Tree a)
 120         join Leaf b2 = b2
 121         join b1 b2 = Node x b1` b2
 122         where
 123                 (x,b1`) = largest b1
 124
 125                 largest :: (Tree a) -> (a,(Tree a))
 126                 largest (Node x b1 Leaf) = (x,b1)
 127                 largest (Node x b1 b2)   = (y,Node x b1 b2`)
 128                 where
 129                         (y,b2`) = largest b2
 130
 131
 132 is_geordend :: // meest algemene type
 133 is_geordend ...
 134
 135 Start = map is_geordend [t0,t1,t2,t3,t4,t5,t6,t7]
 136
 137
 138 is_gebalanceerd :: // meest algemene type
 139 is_gebalanceerd ...
 140
 141 //Start = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7]