sig
  type ('k, 'v) t =
      Empty
    | Node of ('k, 'v) Avltree.t * 'k * 'v * int * ('k, 'v) Avltree.t
    | Leaf of 'k * 'v
  val empty : ('k, 'v) Avltree.t
  val invariant : ('k, 'v) Avltree.t -> compare:('k -> 'k -> int) -> unit
  val add :
    ?replace:bool ->
    ('k, 'v) Avltree.t ->
    compare:('k -> 'k -> int) ->
    added:bool Pervasives.ref -> key:'k -> data:'v -> ('k, 'v) Avltree.t
  val first : ('k, 'v) Avltree.t -> ('k * 'v) option
  val last : ('k, 'v) Avltree.t -> ('k * 'v) option
  val find :
    ('k, 'v) Avltree.t -> compare:('k -> 'k -> int) -> 'k -> 'v option
  val find_and_call :
    ('k, 'v) Avltree.t ->
    compare:('k -> 'k -> int) ->
    'k -> if_found:('v -> 'a) -> if_not_found:('k -> 'a) -> 'a
  val mem : ('k, 'v) Avltree.t -> compare:('k -> 'k -> int) -> 'k -> bool
  val remove :
    ('k, 'v) Avltree.t ->
    removed:bool Pervasives.ref ->
    compare:('k -> 'k -> int) -> 'k -> ('k, 'v) Avltree.t
  val fold :
    ('k, 'v) Avltree.t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a
  val iter : ('k, 'v) Avltree.t -> f:(key:'k -> data:'v -> unit) -> unit
end