Complete the last function (bolded) in OCaml and make sure it can pass the tests at the end.

(******************) (** Starter Code **) (******************)

(* Red-Black Tree Data Type *) (* type data = int *) type color = Red | Black type 'v rbtree = | Empty | Rnode of 'v rbtree * 'v * 'v rbtree (* Red node *) | Bnode of 'v rbtree * 'v * 'v rbtree (* Black node *)

(* Return the color of an rbtree node *) let rbt_color t = match t with Rnode(_,_,_) -> Red | Bnode(_,_,_) | Empty -> Black

(* Result of comparing two values *) (* if a < b, then cmp a b -> Lesser *) (* if a = b, then cmp a b -> Equal *) (* if a > b, then cmp a b -> Greater *) type cmp_result = | Lesser | Equal | Greater

(* compare two data elements of type 'v *) type 'v cmp_fun = 'v -> 'v -> cmp_result

(* Test if t satisfies the red-black tree invariants. * * 1. Does every red node have only black children? * 2. Does every path from root to leaf have the same number of black nodes? *) let rbt_is_invariant (t : 'v rbtree) : bool = (* Check if every red node has only black children *) if t = Empty then true else let rec h tree = match tree with | Empty -> true | Rnode(Rnode(_,_,_),_,_) -> false | Rnode(_,_,Rnode(_,_,_)) -> false | Rnode(left_rbtree,_,right_rbtree) -> h left_rbtree && h right_rbtree | Bnode(left_rbtree,_,right_rbtree) -> h left_rbtree && h right_rbtree in (* Every path has same number of black nodes *) let rec count_black_path tree count = match tree with | Empty -> count | Bnode(left,_,right) -> let left_c = count_black_path left count+1 in let right_c = count_black_path right count+1 in if left_c <> right_c then 0 else left_c | Rnode(left,_,right) -> let left_c = count_black_path left count in let right_c = count_black_path right count in if left_c <> right_c then 0 else left_c in h t && (count_black_path t 0) > 0 (* Test if red-black tree t is sorted. *) let rec rbt_is_sorted (cmp : 'v cmp_fun) (t : 'v rbtree) : bool = let rec inorder (t : 'v rbtree) (acc : 'v list) : 'v list = match t with | Empty -> acc | Bnode (l, v, r) | Rnode (l, v, r) -> inorder l (v :: inorder r acc) in let values = inorder t [] in let rec is_sorted (lst : 'v list) : bool = match lst with | [] | [_] -> true | x :: y :: xs -> match cmp x y with | Lesser -> is_sorted (y :: xs) | _ -> false in is_sorted values

(* Search for element x in red-black tree t. * * Return true if the tree contains x and false if it does not. *) let rec rbt_search (cmp : 'v cmp_fun) (t : 'v rbtree) (x:'v) : bool = match t with | Empty -> false | Bnode(left,curr,right) -> (let res = cmp curr x in match res with | Equal -> true | Lesser -> rbt_search cmp right x | Greater -> rbt_search cmp left x) | Rnode(left,curr,right) -> (let res = cmp curr x in match res with | Equal -> true | Lesser -> rbt_search cmp right x | Greater -> rbt_search cmp left x)

(* Balance constructor for a red-black tree *) let rbt_balance (c:color) (l : 'v rbtree) (v : 'v ) (r : 'v rbtree) : 'v rbtree = match (c,l,v,r) with (* TODO, remove/modify the two cases below *) | (Red,_,_,_) -> Rnode(l,v,r) | (Black,_,_,_) -> Bnode(l,v,r)

(***********) (** Tests **) (***********)

let rbt_balance_int_tests = ("rbt_balance_int", rbt_balance_tester, (=), (=), Some(str_int_rbtree, str_int_rbtree), [ (Some("Case A"), Bnode(Rnode(r1,2,Empty), 3, Empty), Ok(Rnode(b1,2,b3))); ])

let rbt_balance_str_tests = ("rbt_balance_str", rbt_balance_tester, (=), (=), Some(str_str_rbtree, str_str_rbtree), [ (Some("Case A"), Bnode(Rnode(ra,"b",Empty), "c", Empty), Ok(Rnode(ba,"b",bc))) ])