|
|
— |
pl:prolog:pllib:dictionary_modification [2019/06/27 15:50] (aktualna) |
| ====== Dictionary modification ====== |
| {{tag>trees}} |
| ===== Description ===== |
| Inserting and deleting in the 2-3 dictionary. |
| |
| **Source**: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7. |
| ===== Download ===== |
| Program source code: {{dictionary_modification.pl}} |
| ===== Listing ===== |
| <code prolog> |
| % 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. |
| </code> |
| ===== Comments ===== |
| |