Insertion into the binary dictionary at any level of the tree.
Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.
% Figure 9.15 Insertion into the binary dictionary at any level of the tree.
% 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)).
gt(X,Root):-X>Root.