Advertisement
raedr7n

Check if RB-Tree has more B nodes

Oct 24th, 2021 (edited)
1,344
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. type 'a rb_tree =
  2.     | Black of 'a rb_tree * 'a * 'a rb_tree
  3.     | Red of 'a rb_tree * 'a * 'a rb_tree
  4.     | Nil
  5.  
  6. let more_black tree =
  7.     let rec aux sums = function
  8.         | Black (l, _, r) -> sigma sums (1, 0) (aux sums l) (aux sums r)
  9.         | Red (l, _, r) -> sigma sums (0, 1) (aux sums l) (aux sums r)
  10.         | Nil -> sums
  11.     and sigma (a, b) (c, d) (e, f) (g, h) = (a + c + e + g, b + d + f + h) in
  12.     let blacks, reds = aux (0, 0) tree in
  13.     blacks > reds
  14.  
  15. let rbt = Red (Black (Black (Nil, 4, Red (Nil, 11, Nil)), 1, Nil), 8, Red (Nil, 4, Black (Nil, 7, Black (Nil, 4, Nil))))
  16.  
  17. let () = more_black rbt |> string_of_bool |> print_endline
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement