Inserting and deleting in the 2-3 dictionary.

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Program source code: dictionary_modification.pl

%  Figure 10.6  Inserting and deleting in the 2-3 dictionary. 
%  In this program, an attempt to insert a duplicate item will fail.
 
 
% Insertion in the 2-3 dictionary
 
add23( Tree, X, Tree1)  :-                  % Add X to Tree giving Tree1
   ins( Tree, X, Tree1).                    % Tree grows in breadth
 
add23( Tree, X, n2( T1, M2, T2))  :-        % Tree grows upwards
   ins( Tree, X, T1, M2, T2).
 
del23( Tree, X, Tree1)  :-                  % Delete X from Tree giving Tree1
   add23( Tree1, X, Tree).
 
ins( nil, X, l(X)).
 
ins( l(A), X, l(A), X, l(X))  :-
   gt( X, A).
 
ins( l(A), X, l(X), A, l(A))  :-
   gt( A, X).
 
 
ins( n2( T1, M , T2), X, n2( NT1, M, T2))  :-
   gt( M, X),
   ins( T1, X, NT1).
 
ins( n2( T1, M, T2), X, n3( NT1a, Mb, NT1b, M, T2))  :-
   gt( M, X),
   ins( T1, X, NT1a, Mb, NT1b).
 
 
ins( n2( T1, M, T2), X, n2( T1, M, NT2))  :-
   gt( X, M),
   ins( T2, X, NT2).
 
ins( n2( T1, M, T2), X, n3( T1, M, NT2a, Mb, NT2b))  :-
   gt( X, M),
   ins( T2, X, NT2a, Mb, NT2b).
 
 
ins( n3( T1, M2, T2, M3, T3), X, n3( NT1, M2, T2, M3, T3))  :-
   gt( M2, X),
   ins( T1, X, NT1).
 
ins( n3( T1, M2, T2, M3, T3), X, n2( NT1a, Mb, NT1b), M2, n2( T2, M3, T3)) :-
   gt( M2, X),
   ins( T1, X, NT1a, Mb, NT1b).
 
 
ins( n3( T1, M2, T2, M3, T3), X, n3( T1, M2, NT2, M3, T3))  :-
   gt( X, M2), gt( M3, X),
   ins( T2, X, NT2).
 
ins( n3( T1, M2, T2, M3, T3), X, n2( T1, M2, NT2a), Mb, n2( NT2b, M3, T3)) :-
   gt( X, M2), gt( M3, X),
   ins( T2, X, NT2a, Mb, NT2b).
 
 
ins( n3( T1, M2, T2, M3, T3), X, n3( T1, M2, T2, M3, NT3))  :-
   gt( X, M3),
   ins( T3, X, NT3).
 
ins( n3( T1, M2, T2, M3, T3), X, n2( T1, M2, T2), M3, n2( NT3a, Mb, NT3b))  :-
   gt( X, M3),
   ins( T3, X, NT3a, Mb, NT3b).
 
gt(X,Root):-X>Root.