%  Figure 10.10  AVL-dictionary insertion. In this program, an attempt
%  to insert a duplicate will fail. See Fig. 10.9 for combine.


% addavl( Tree, X, NewTree): insertion into AVL-dictionary
%    Tree = t( Left, Root, Right)/HeightOfTree
%    Empty tree = nil/0


addavl( nil/0, X, t(nil/0,X,nil/0)/1).      % Add X to empty tree

addavl( t(L,Y,R)/Hy, X, NewTree)  :-        % Add X to nonempty tree
   gt( Y, X),
   addavl( L, X, t(L1,Z,L2)/_),             % Add into left subtree
   combine( L1, Z, L2, Y, R, NewTree).      % Combine ingredients of NewTree

addavl( t(L,Y,R)/Hy, X, NewTree)  :-
   gt( X, Y),
   addavl( R, X, t(R1,Z,R2)/_),             % Add into right subtree
   combine( L, Y, R1, Z, R2, NewTree).

combine( T1/H1, A, t(T21,B,T22)/H2, C, T3/H3,
         t( t(T1/H1,A,T21)/Ha, B, t(T22,C,T3/H3)/Hc)/Hb )  :-
   H2 > H1, H2 > H3,                        % Middle subtree tallest
   Ha is H1 + 1,
   Hc is H3 + 1,
   Hb is Ha + 1.

combine( T1/H1, A, T2/H2, C, T3/H3,
         t( T1/H1, A, t(T2/H2,C,T3/H3)/Hc)/Ha )  :-
   H1 >= H2, H1 >= H3,                      % Tall left subtree
   max1( H2, H3, Hc),
   max1( H1, Hc, Ha).

combine( T1/H1, A, T2/H2, C, T3/H3,
         t( t(T1/H1,A,T2/H2)/Ha, C, T3/H3)/Hc )  :-
   H3 >= H2, H3 >= H1,                      % Tall right subtree
   max1( H1, H2, Ha),
   max1( Ha, H3, Hc).


max1( U, V, M)  :-           % M is 1 + max. of U and V
   U > V, !, M is U + 1;
   M is V + 1.

gt(X,ROOT) :- X>ROOT.