week7/camil/BinSearchTree.icl

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