赤黒木

赤黒木のinsertをOCamlで書きました.
removeはもっと全然面倒で, 書いてはみたけどデバッグに途方に暮れ挫折しました.

module type OrderedType =
sig
  type t
  val compare : t -> t -> int
end

module Make(Ord : OrderedType) =
struct
  type elt = Ord.t
  type t = R of t * elt * t | B of t * elt * t | Nil

  let is_black = function
    | R _ -> false
    | _ -> true

  (*
    [insert e tree] inserts [e] into [tree] and returns it.
    If any element [e'] exists and [Ord.compare e e' = 0] is true,
    it does nothing.
   *)
  let insert e tree =
    let rec ins e = function
      | Nil -> R (Nil, e, Nil)
      | R (l, e', r) ->
          (match Ord.compare e e' with
            | 0 -> R (l, e, r)
            | b when b > 0 -> R (l, e', ins e r)
            | b when b < 0 -> R (ins e l, e', r)
            | _ -> assert false)
      | B (l, e', r) ->
          let rec fixr = function
            | B (R (ly, y, ry), w, R (lz, z, R (lx, x, rx))) ->
                R (B (ly, y, ry), w, B (lz, z, R (lx, x, rx)))
            | B (y, w, R (lz, z, R (lx, x, rx))) when is_black y ->
                B (R (y, w, lz), z, R (lx, x, rx))
            | B (lw, w, R (R (lx, x, rx), z, rz)) ->
                fixr (B (lw, w, R (lx, x, R (rx, z, rz))))
            | x -> x
          in
          let rec fixl = function
            | B (R (R (lx, x, rx), z, rz), w, R (ly, y, ry)) ->
                R (B (R (lx, x, rx), z, rz), w, B (ly, y, ry))
            | B (R (R (lx, x, rx), z, rz), w, y) when is_black y ->
                B (R (lx, x, rx), z, R (rz, w, y))
            | B (R (lz, z, R (lx, x, rx)), w, rw) ->
                fixl (B (R (R (lz, z, lx), x, rx), w, rw))
            | x -> x
          in
          (match Ord.compare e e' with
            | 0 -> B (l, e, r)
            | b when b > 0 -> fixr (B (l, e', ins e r))
            | b when b < 0 -> fixl (B (ins e l, e', r))
            | _ -> assert false)
    in
    match ins e tree with
      | R (l, e, r) | B (l, e, r) ->
          B (l, e, r)
      | Nil -> assert false
end

これでもそれなりに気分良く書けて満足してたんだけど, 世の中はとんでもなく進んでいて, http://tinyurl.com/yqrr6pとかうーん. 場合分けの数が極端に少ないなあ. どうなってんの？

ちなみにいつものように赤黒木の実装で参考にしたのはamazon:Introduction to Algorithmsで紹介されているもの.