% taken from % http://www.pearsoned.co.uk/highereducation/resources/bratkoprologprogrammingforartificialintelligence3e/ % Figure 9.10 Inserting an item as a leaf into the binary dictionary. % addleaf( Tree, X, NewTree): % inserting X as a leaf into binary dictionary Tree gives NewTree gt(X,Y) :- X > Y. addleaf( nil, X, t( nil, X, nil)). addleaf( t( Left, X, Right), X, t( Left, X, Right)). addleaf( t( Left, Root, Right), X, t( Left1, Root, Right)) :- gt( Root, X), addleaf( Left, X, Left1). addleaf( t( Left, Root, Right), X, t( Left, Root, Right1)) :- gt( X, Root), addleaf( Right, X, Right1). % 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). % Figure 9.15 Insertion into the binary dictionary at any level of the tree. % add( Tree, X, NewTree): % inserting X at any level of binary dictionary Tree gives NewTree add( Tree, X, NewTree) :- addroot( Tree, X, NewTree). % Add X as new root add( t( L, Y, R), X, t( L1, Y, R)) :- % Insert X into left subtree gt( Y, X), add( L, X, L1). add( t( L, Y, R), X, t( L, Y, R1)) :- % Insert X into right subtree gt( X, Y), add( R, X, R1). % addroot( Tree, X, NewTree): % inserting X as the root into Tree gives NewTree addroot( nil, X, t( nil, X, nil)). % Insert into empty tree addroot( t( L, Y, R), X, t( L1, X, t( L2, Y, R))) :- gt( Y, X), addroot( L, X, t( L1, X, L2)). addroot( t( L, Y, R), X, t( t( L, Y, R1), X, R2)) :- gt( X, Y), addroot( R, X, t( R1, X, R2)). q1(T4) :- T3 = t(t(nil, 3, nil), 4, t(nil, 8, nil)), addleaf(T3,6,T4). q2(T6) :- T4 = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, nil)), addleaf(T4,10,T5), del(T5,8,T6). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% /* % inserting some elements ?- addleaf(nil,4,T1), addleaf(T1,3,T2), addleaf(T2,8,T3). T1 = t(nil, 4, nil) T2 = t(t(nil, 3, nil), 4, nil) T3 = t(t(nil, 3, nil), 4, t(nil, 8, nil)) ; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % insert 6 in T3 ?- T3 = t(t(nil, 3, nil), 4, t(nil, 8, nil)), addleaf(T3,6,T4). T3 = t(t(nil, 3, nil), 4, t(nil, 8, nil)) T4 = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, nil)) ; No % tracing it! ?- trace. 1 ?- trace. true. [trace] 1 ?- q1(L). Call: (6) q1(_G442) ? creep Call: (7) _G525=t(t(nil, 3, nil), 4, t(nil, 8, nil)) ? creep Exit: (7) t(t(nil, 3, nil), 4, t(nil, 8, nil))=t(t(nil, 3, nil), 4, t(nil, 8, nil)) ? creep Call: (7) addleaf(t(t(nil, 3, nil), 4, t(nil, 8, nil)), 6, _G442) ? creep Call: (8) gt(4, 6) ? creep ^ Call: (9) 4>6 ? creep ^ Fail: (9) 4>6 ? creep Fail: (8) gt(4, 6) ? creep Redo: (7) addleaf(t(t(nil, 3, nil), 4, t(nil, 8, nil)), 6, _G442) ? creep Call: (8) gt(6, 4) ? creep ^ Call: (9) 6>4 ? creep ^ Exit: (9) 6>4 ? creep Exit: (8) gt(6, 4) ? creep Call: (8) addleaf(t(nil, 8, nil), 6, _G520) ? creep Call: (9) gt(8, 6) ? creep ^ Call: (10) 8>6 ? creep ^ Exit: (10) 8>6 ? creep Exit: (9) gt(8, 6) ? creep Call: (9) addleaf(nil, 6, _G522) ? creep Exit: (9) addleaf(nil, 6, t(nil, 6, nil)) ? creep Exit: (8) addleaf(t(nil, 8, nil), 6, t(t(nil, 6, nil), 8, nil)) ? creep Exit: (7) addleaf(t(t(nil, 3, nil), 4, t(nil, 8, nil)), 6, t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, nil))) ? creep Exit: (6) q1(t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, nil))) ? creep L = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, nil)) . [trace] 2 ?- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % insert element 10, 9 and 17 ?- T4 = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, nil)) , addleaf(T4,10,T5), addleaf(T5,9,T6), addleaf(T6,17,T7). T4 = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, nil)), T5 = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, t(nil, 10, nil))), T6 = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, nil))), T7 = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, t(nil, 17, nil)))) ; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % delete 8 from T5 ?- T5 = t(t(nil, 3, nil), 5, t(t(nil, 6, nil), 8, t(nil, 10, nil))), del(T5,8,T6). T5 = t(t(nil, 3, nil), 5, t(t(nil, 6, nil), 8, t(nil, 10, nil))) T6 = t(t(nil, 3, nil), 5, t(t(nil, 6, nil), 10, nil)) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % delete 8 from T7 */ q3(T8):- T7 = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, t(nil, 17, nil)))), del(T7,8,T8). /* [trace] 2 ?- q3(L). Call: (6) q3(_G442) ? creep Call: (7) _G541=t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, t(nil, 17, nil)))) ? creep Exit: (7) t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, t(nil, 17, nil))))=t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, t(nil, 17, nil)))) ? creep Call: (7) del(t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, t(nil, 17, nil)))), 8, _G442) ? creep Call: (8) gt(4, 8) ? creep ^ Call: (9) 4>8 ? creep ^ Fail: (9) 4>8 ? creep Fail: (8) gt(4, 8) ? creep Redo: (7) del(t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, t(nil, 17, nil)))), 8, _G442) ? creep Call: (8) gt(8, 4) ? creep ^ Call: (9) 8>4 ? creep ^ Exit: (9) 8>4 ? creep Exit: (8) gt(8, 4) ? creep Call: (8) del(t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, t(nil, 17, nil))), 8, _G536) ? creep Call: (9) delmin(t(t(nil, 9, nil), 10, t(nil, 17, nil)), _G539, _G540) ? creep Call: (10) delmin(t(nil, 9, nil), _G539, _G542) ? creep Exit: (10) delmin(t(nil, 9, nil), 9, nil) ? creep Exit: (9) delmin(t(t(nil, 9, nil), 10, t(nil, 17, nil)), 9, t(nil, 10, t(nil, 17, nil))) ? creep Exit: (8) del(t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, t(nil, 17, nil))), 8, t(t(nil, 6, nil), 9, t(nil, 10, t(nil, 17, nil)))) ? creep Exit: (7) del(t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 8, t(t(nil, 9, nil), 10, t(nil, 17, nil)))), 8, t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 9, t(nil, 10, t(nil, 17, nil))))) ? creep Exit: (6) q3(t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 9, t(nil, 10, t(nil, 17, nil))))) ? creep L = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 9, t(nil, 10, t(nil, 17, nil)))) . %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% q4(J) :- L = t(t(nil, 3, nil), 4, t(t(nil, 6, nil), 9, t(nil, 10, t(nil, 17, nil)))) , add 8 ?- | add(nil,3,D1), add(D1,5,D2), add(D2,1,D3), add(D3,6,D4), add(DD,5,D4). Call: (7) add(nil, 3, _G986) ? skip Exit: (7) add(nil, 3, t(nil, 3, nil)) ? creep Call: (7) add(t(nil, 3, nil), 5, _G990) ? skip Exit: (7) add(t(nil, 3, nil), 5, t(t(nil, 3, nil), 5, nil)) ? creep Call: (7) add(t(t(nil, 3, nil), 5, nil), 1, _G994) ? skip Exit: (7) add(t(t(nil, 3, nil), 5, nil), 1, t(nil, 1, t(t(nil, 3, nil), 5, nil))) ? creep Call: (7) add(t(nil, 1, t(t(nil, 3, nil), 5, nil)), 6, _G998) ? skip Exit: (7) add(t(nil, 1, t(t(nil, 3, nil), 5, nil)), 6, t(t(nil, 1, t(t(nil, 3, nil), 5, nil)), 6, nil)) ? creep Call: (7) add(_G1000, 5, t(t(nil, 1, t(t(nil, 3, nil), 5, nil)), 6, nil)) ? creep Call: (8) addroot(_G1000, 5, t(t(nil, 1, t(t(nil, 3, nil), 5, nil)), 6, nil)) ? creep Fail: (8) addroot(_G1000, 5, t(t(nil, 1, t(t(nil, 3, nil), 5, nil)), 6, nil)) ? creep Redo: (7) add(_G1000, 5, t(t(nil, 1, t(t(nil, 3, nil), 5, nil)), 6, nil)) ? creep Call: (8) gt(6, 5) ? creep ^ Call: (9) 6>5 ? creep ^ Exit: (9) 6>5 ? creep Exit: (8) gt(6, 5) ? creep Call: (8) add(_G1352, 5, t(nil, 1, t(t(nil, 3, nil), 5, nil))) ? creep Call: (9) addroot(_G1352, 5, t(nil, 1, t(t(nil, 3, nil), 5, nil))) ? creep Fail: (9) addroot(_G1352, 5, t(nil, 1, t(t(nil, 3, nil), 5, nil))) ? creep Redo: (8) add(_G1352, 5, t(nil, 1, t(t(nil, 3, nil), 5, nil))) ? creep Call: (9) gt(1, 5) ? creep ^ Call: (10) 1>5 ? creep ^ Fail: (10) 1>5 ? creep Fail: (9) gt(1, 5) ? creep Redo: (8) add(_G1352, 5, t(nil, 1, t(t(nil, 3, nil), 5, nil))) ? creep Call: (9) gt(5, 1) ? creep ^ Call: (10) 5>1 ? creep ^ Exit: (10) 5>1 ? creep Exit: (9) gt(5, 1) ? creep Call: (9) add(_G1358, 5, t(t(nil, 3, nil), 5, nil)) ? creep Call: (10) addroot(_G1358, 5, t(t(nil, 3, nil), 5, nil)) ? creep Call: (11) gt(5, 3) ? creep ^ Call: (12) 5>3 ? creep ^ Exit: (12) 5>3 ? creep Exit: (11) gt(5, 3) ? creep Call: (11) addroot(_G1362, 5, t(nil, 5, nil)) ? creep Exit: (11) addroot(nil, 5, t(nil, 5, nil)) ? creep Exit: (10) addroot(t(nil, 3, nil), 5, t(t(nil, 3, nil), 5, nil)) ? creep Exit: (9) add(t(nil, 3, nil), 5, t(t(nil, 3, nil), 5, nil)) ? creep Exit: (8) add(t(nil, 1, t(nil, 3, nil)), 5, t(nil, 1, t(t(nil, 3, nil), 5, nil))) ? creep Exit: (7) add(t(t(nil, 1, t(nil, 3, nil)), 6, nil), 5, t(t(nil, 1, t(t(nil, 3, nil), 5, nil)), 6, nil)) ? creep D1 = t(nil, 3, nil), D2 = t(t(nil, 3, nil), 5, nil), D3 = t(nil, 1, t(t(nil, 3, nil), 5, nil)), D4 = t(t(nil, 1, t(t(nil, 3, nil), 5, nil)), 6, nil), DD = t(t(nil, 1, t(nil, 3, nil)), 6, nil)