Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:pllib:avl_dict_insert [2019/06/27 15:50] |
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 ===== | ||
