% Figure 9.15  Insertion into the binary dictionary at any level of the tree.

gt( X,Y) :- number(X), number(Y), X > Y, !.

% add( Tree, X, NewTree):
%   inserting X at any level of binary dictionary Tree gives NewTree

add( Tree, X, NewTree)  :-
   addroot( Tree, X, NewTree).               % Add X as new root

add( t( L, Y, R), X, t( L1, Y, R))  :-       % Insert X into left subtree
   gt( Y, X),
   add( L, X, L1).

add( t( L, Y, R), X, t( L, Y, R1))  :-       % Insert X into right subtree
   gt( X, Y),
   add( R, X, R1).

% addroot( Tree, X, NewTree):
%   inserting X as the root into Tree gives NewTree

addroot( nil, X, t( nil, X, nil)).           % Insert into empty tree

addroot( t( L, Y, R), X, t( L1, X, t( L2, Y, R)))  :-
   gt( Y, X),
   addroot( L, X, t( L1, X, L2)).

addroot( t( L, Y, R), X, t( t( L, Y, R1), X, R2))  :-
   gt( X, Y),
   addroot( R, X, t( R1, X, R2)).

test( D1,D2,D3,D,DD) :-
 add( nil,3,D1),
write('*****'), nl,
 add( D1,5,D2),
write('*****'), nl,
 add( D2,1,D3),
write('*****'), nl,
 add( D3,6,D),
write('*****'), nl,
 add( DD,5,D).

% This test requires the program of fig9_17.pl for display purposes

test1( D1,D2,D3,D,DD) :-
 add( nil,3,D1), show(D1),
 nl, write('*****'), nl,
 add( D1,5,D2), show(D2),
 nl, write('*****'), nl,
 add( D2,1,D3), show(D3),
 nl, write('*****'), nl,
 add( D3,6,D), show(D),
 nl, write('*****'), nl,
 add( DD,5,D), show(DD).