SHOW:
|
|
- or go back to the newest paste.
| 1 | - | type 'a bin_tree = |
| 1 | + | type 'a rb_tree = |
| 2 | - | | Red of 'a bin_tree * 'a * 'a bin_tree |
| 2 | + | | Black of 'a rb_tree * 'a * 'a rb_tree |
| 3 | - | | Blue of 'a bin_tree * 'a * 'a bin_tree |
| 3 | + | | Red of 'a rb_tree * 'a * 'a rb_tree |
| 4 | | Nil | |
| 5 | ||
| 6 | - | let more_blue tree = |
| 6 | + | let more_black tree = |
| 7 | let rec aux sums = function | |
| 8 | - | | Blue (l, _, r) -> qor sums (1, 0) (aux sums l) (aux sums r) |
| 8 | + | | Black (l, _, r) -> sigma sums (1, 0) (aux sums l) (aux sums r) |
| 9 | - | | Red (l, _, r) -> qor sums (0, 1) (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 qor (a, b) (c, d) (e, f) (g, h) = (a + c + e + g, b + d + f + h) in |
| 11 | + | and sigma (a, b) (c, d) (e, f) (g, h) = (a + c + e + g, b + d + f + h) in |
| 12 | - | let blues, reds = aux (0, 0) tree in |
| 12 | + | let blacks, reds = aux (0, 0) tree in |
| 13 | - | blues > reds |
| 13 | + | blacks > reds |
| 14 | ||
| 15 | - | let rbt = Red (Blue (Blue(Nil, 4, Red (Nil, 11, Nil)), 1, Nil), 8, Red (Nil, 4, Blue(Nil, 7, Blue (Nil, 4, Nil)))) |
| 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_blue rbt |> string_of_bool |> print_endline |
| 17 | + | let () = more_black rbt |> string_of_bool |> print_endline |
