week7/camil/BinSearchTree.icl

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