Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

pl:prolog:pllib:avl_dict_insert [2019/06/27 15:50] (aktualna)
Linia 1: Linia 1:
 +====== Avl dict insert ======
 +{{tag>​trees}}
 +===== 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 =====
 +<code prolog>
 +%  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.
 +</​code>​
 +===== Comments =====
  
pl/prolog/pllib/avl_dict_insert.txt · ostatnio zmienione: 2019/06/27 15:50 (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