signature BTREE_CONTENTS =
sig
   type t
   val compare : t * t -> order
end
 
functor BTree(X : BTREE_CONTENTS) =
struct
   type t = X.t
 
   datatype btree =
      Leaf
    | Value of X.t
    | Branch of X.t * btree * btree
 
   fun contains(_, Leaf) = false
     | contains(v, Value v') =
         X.compare(v, v') = EQUAL
     | contains(v, Branch (v', left, right)) =
         (case X.compare(v, v') of
            EQUAL   => true
          | LESS    => contains(v, left)
          | GREATER => contains(v, right));
 
   fun insert(v, Leaf) = Value v
     | insert(v, t as Value v') =
         (case X.compare(v, v') of
            EQUAL   => t
          | LESS    => Branch (v', Value v, Leaf)
          | GREATER => Branch (v', Leaf, Value v))
     | insert(v, t as Branch (v', left, right)) =
         (case X.compare(v, v') of
            EQUAL   => t
          | LESS    => Branch (v', insert(v, left), right)
          | GREATER => Branch (v', left, insert(v, right)))
 
   fun toList(Leaf) = []
     | toList(Value v) = [v]
     | toList(Branch (v, left, right)) =
         toList(left) @ [v] @ toList(right)
 
   fun height(Leaf) = 0
     | height(Value _) = 1
     | height(Branch (_, left, right)) =
         Int.max(height(left), height(right)) + 1
 
   fun size(Leaf) = 0
     | size(Value _) = 1
     | size(Branch (_, left, right)) =
         1 + size(left) + size(right)
 
   fun isBalanced(Leaf) = true
     | isBalanced(Value _) = true
     | isBalanced(Branch (_, left, right)) =
         Int.abs(height(left) - height(right)) <= 1
         andalso isBalanced(left)
         andalso isBalanced(right)
end
 
structure IntBTree = BTree(type t = int; val compare = Int.compare)