structure TTTree = struct
        datatype tttree = Two of int * tttree * tttree |
                Three of int * int * tttree * tttree * tttree |
                Leaf of int;

        datatype oneOrTwo = S of tttree |
                P of int * tttree * tttree;

        (* create(i) creates a 2-3 tree with one leaf,
           labeled i *)
        fun create(i) = Leaf(i);

        (* lookup(x,T) tells whether integer x is at a leaf of
           2-3 tree T *)
        fun lookup(x,Leaf(i)) = (x=i)
        |   lookup(x,Two(i,T1,T2)) =
                        if x<i then lookup(x,T1)
                        else lookup(x,T2)
        |   lookup(x,Three(i,j,T1,T2,T3)) =
                        if x<i then lookup(x,T1)
                        else if x<j then lookup(x,T2)
                        else (* x>=j *) lookup(x,T3);

        (* the following 5 "group" functions are auxiliaries
           used in the function insert1 below.
           See explanation in the text. *)
        fun groupUT(i,S(T1),T2) = S(Two(i,T1,T2))
        |   groupUT(i,P(j,T1,T2),T3) = S(Three(j,i,T1,T2,T3));

        fun groupTU(i,T1,S(T2)) = S(Two(i,T1,T2))
        |   groupTU(i,T1,P(j,T2,T3)) = S(Three(i,j,T1,T2,T3));

        fun groupUTT(i,j,S(T1),T2,T3) = S(Three(i,j,T1,T2,T3))
        |   groupUTT(i,j,P(k,T1,T2),T3,T4) =
                        P(i,Two(k,T1,T2),Two(j,T3,T4));

        fun groupTUT(i,j,T1,S(T2),T3) = S(Three(i,j,T1,T2,T3))
        |   groupTUT(i,j,T1,P(k,T2,T3),T4) =
                        P(k,Two(i,T1,T2),Two(j,T3,T4));

        fun groupTTU(i,j,T1,T2,S(T3)) = S(Three(i,j,T1,T2,T3))
        |   groupTTU(i,j,T1,T2,P(k,T3,T4)) =
                        P(j,Two(i,T1,T2),Two(k,T3,T4));

        (* insert1(x,T) inserts integer x into 2-3 tree T and
           returns a oneOrTwo, that is, a 2-3 tree wrapped in S
           or two 2-3 trees wrapped in P *)
        fun insert1(x,Leaf(i)) =
                        if x<i then P(i,Leaf(x),Leaf(i))
                        else if x>i then P(x,Leaf(i),Leaf(x))
                        else S(Leaf(i))
        |   insert1(x,Two(i,T1,T2)) =
                        if x<i then
                                groupUT(i,insert1(x,T1),T2)
                        else (* x>=i *)
                                groupTU(i,T1,insert1(x,T2))
        |   insert1(x,Three(i,j,T1,T2,T3)) =
                        if x<i then
                                groupUTT(i,j,insert1(x,T1),T2,T3)
                        else if x<j then
                                groupTUT(i,j,T1,insert1(x,T2),T3)
                        else (* x>=j *)
                                groupTTU(i,j,T1,T2,insert1(x,T3));

        (* unwrap(X) either removes the one tree from an S or
           creates a new node with the two subtrees found
           inside a P. *)
        fun unwrap(S(T)) = T
        |   unwrap(P(i,T1,T2)) = Two(i,T1,T2);

        (* insert(x,T) inserts x into 2-3 tree T. *)
        fun insert(x,T) = unwrap(insert1(x,T))
end;