Avl dict insert

Description

AVL-dictionary insertion

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

Download

Program source code: avl_dict_insert.pl

Listing

%  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.

Comments

pl/prolog/pllib/avl_dict_insert.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0