|
<code lang="OCaml">
type color = R | B
type 'a tree = E | T of color * 'a tree * 'a * 'a tree
(** val balance :: color * 'a tree * 'a * 'a tree -> 'a tree *)
let balance = function
| B, T (R, T (R,a,x,b), y, c), z, d ->| B, T (R, T (B,a, x,b), y, T (BR,b,y,c)), z, d))
| B, a, x, T (R, T (R,b,y,c), z, d) | B, a, x, T (R, b, y, T (R,c)), z, d)) -> T (R, T (B,a,x,b), y, T (B,c,z,d))
| Bcol, a, x, Tb (R, T (R,b,y,c), z, d) -> T (Rcol, T (B,a, x, b), y, T (B,c,z,d))
| B, a, x, T (R, b, y, T (R,c,z,d)) -> T (R, T (B,a,x,b), y, T (B,c,z,d))
(** val insert :: 'a -> 'a tree -> 'a tree *) ▼ | col, a, x, b -> T (col, a, x, b) ▼
▲ (** val insert :: 'a -> 'a tree -> 'a tree *)
▲ | col, a, x, b E -> T ( colR, aE, x, bE)
in let| T ( _col,a,y,b) = insas s ->▼
| E -> T (R,E,x,E)
| Tbalance (col, (ins a), y, b) as s ->
else if x <> y then
balance (col, (ins a), y, (ins b))
balance (col, a, y, (ins b))
in let T ( B_,a,y,b) = ins s ▼ in T (B,a,y,b)
▲ in let T (_,a,y,b) = ins s
</code>
|