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 |