// Mart Lubbers, s4109503
// Camil Staps, s4498062

implementation module BinSearchTree

import StdEnv
import BinTree

z0 = Leaf
//  Leaf

z1 = insertTree 50 z0
//          50
//          |
//     -------------
//     |           |
//    Leaf        Leaf

z2 = insertTree 10 z1
//           50
//           |
//      -------------
//      |           |
//      10         Leaf
//      |
//  ---------
//  |       |
// Leaf    Leaf

z3 = insertTree 75 z2
//             50
//             |
//      ---------------
//      |             |
//      10            75
//      |             |
//  ---------     ---------
//  |       |     |       |
// Leaf    Leaf  Leaf    Leaf

z4 = insertTree 80 z3
//             50
//             |
//      ---------------
//      |             |
//      10            75
//      |             |
//  ---------     ---------
//  |       |     |       |
// Leaf    Leaf  Leaf     80
//                        |
//                    ---------
//                    |       |
//                   Leaf    Leaf

z5 = insertTree 77 z4
//             50
//             |
//      ---------------
//      |             |
//      10            75
//      |             |
//  ---------     ---------
//  |       |     |       |
// Leaf    Leaf  Leaf     77
//                        |
//                    ---------
//                    |       |
//                   Leaf     80
//                            |
//                        ---------
//                        |       |
//                       Leaf    Leaf

z6 = insertTree 10 z5
//               50
//               |
//         ---------------
//         |             |
//         10            75
//         |             |
//     ---------     ---------
//     |       |     |       |
//     10     Leaf  Leaf     77
//     |                     |
//  ---------            ---------
//  |       |            |       |
// Leaf    Leaf         Leaf     80
//                               |
//                           ---------
//                           |       |
//                          Leaf    Leaf

z7 = insertTree 75 z6
//                50
//                |
//         ----------------
//         |              |
//         10             75
//         |              |
//     ---------     -----------
//     |       |     |         |
//     10     Leaf   75        77
//     |             |         |
//  ---------     ------    -------
//  |       |     |    |    |     |
// Leaf    Leaf  Leaf Leaf Leaf   80
//                                |
//                            ---------
//                            |       |
//                           Leaf    Leaf

z8 = deleteTree 50 z7
//                10
//                |
//         ----------------
//         |              |
//         10             75
//         |              |
//     ---------     -----------
//     |       |     |         |
//    Leaf    Leaf   75        77
//                   |         |
//                ------    -------
//                |    |    |     |
//               Leaf Leaf Leaf   80
//                                |
//                            ---------
//                            |       |
//                           Leaf    Leaf

//  Uit het diktaat, blz. 73:
insertTree :: a (Tree a) -> Tree a | Ord a
insertTree e Leaf = Node e Leaf Leaf
insertTree e (Node x le ri)
| e <= x = Node x (insertTree e le) ri
| e >  x = Node x le (insertTree e ri)

deleteTree :: a (Tree a) -> (Tree a) | Eq, Ord a
deleteTree e Leaf = Leaf
deleteTree e (Node x le ri)
| e <  x = Node x (deleteTree e le) ri
| e == x = join le ri
| e >  x = Node x le (deleteTree e ri)
where
    join :: (Tree a) (Tree a) -> (Tree a)
    join Leaf b2 = b2
    join b1 b2 = Node x b1` b2
    where
        (x,b1`) = largest b1
        
        largest :: (Tree a) -> (a,(Tree a))
        largest (Node x b1 Leaf) = (x,b1)
        largest (Node x b1 b2)   = (y,Node x b1 b2`)
        where
            (y,b2`) = largest b2


is_geordend :: (Tree a) -> Bool | Ord a // meest algemene type
is_geordend Leaf = True
is_geordend (Node x le ri) = (foldr (&&) True (map ((>) x) (members le))) && (foldr (&&) True (map ((<=) x) (members ri))) && is_geordend le && is_geordend ri
where
    members :: (Tree a) -> [a]
    members Leaf = []
    members (Node x le ri) = [x:(members le) ++ (members ri)]

//Start = map is_geordend [t0,t1,t2,t3,t4,t5,t6,t7]

is_gebalanceerd :: (Tree a) -> Bool | Ord a // meest algemene type
is_gebalanceerd Leaf = True
is_gebalanceerd (Node x le ri) = abs ((depth le) - (depth ri)) <= 1 && is_gebalanceerd le && is_gebalanceerd ri
where
    depth :: (Tree a) -> Int
    depth Leaf = 0
    depth (Node x le ri) = max (depth le) (depth ri) + 1

//Start = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7]