Deleting X from binary dictionary Tree gives NewTree.

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

Program source code: delete_from_tree.pl

% Figure 9.13  Deleting from the binary dictionary.
 
 
% del( Tree, X, NewTree):
%   deleting X from binary dictionary Tree gives NewTree
 
del( t( nil, X, Right), X, Right).
 
del( t( Left, X, nil), X, Left).
 
del( t( Left, X, Right), X, t( Left, Y, Right1))  :-
   delmin( Right, Y, Right1).
 
del( t( Left, Root, Right), X, t( Left1, Root, Right))  :-
   gt( Root, X),
   del( Left, X, Left1).
 
del( t( Left, Root, Right), X, t( Left, Root, Right1))  :-
   gt( X, Root),
   del( Right, X, Right1).
 
% delmin( Tree, Y, NewTree):
%   delete minimal item Y in binary dictionary Tree producing NewTree
 
delmin( t( nil, Y, R), Y, R).
 
delmin( t( Left, Root, Right), Y, t( Left1, Root, Right))  :-
   delmin( Left, Y, Left1).