signature TREE = sig
  type ('k, 'v) t

  val empty: ('k, 'v) t

  type 'k cmp = 'k -> 'k -> order

  val insert: 'k cmp -> ('k, 'v) t -> 'k -> 'v -> 'v option * ('k, 'v) t

  val delete: 'k cmp -> ('k, 'v) t -> 'k -> 'v option * ('k, 'v) t

  val lookup: 'k cmp -> ('k, 'v) t -> 'k -> 'v option
  val lookup2: 'k cmp -> ('k, 'v) t -> 'k ->
        ('v option -> 'a * 'v option) -> 'a * ('k, 'v) t

  val print: ('k, 'v) t -> ('k -> string) -> ('v -> string) -> unit
  val size: ('k, 'v) t -> int
end