встав( в2( Д1, М, Д2), X, в3( Д1, М, НД2а, Мб, НД2б) ) :-
больше( X, М),
встав( Д2, X, НД2а, Мб, НД2б).
встав( в3( Д1, M2, Д2, М3, Д3), X,
в3( НД1, M2, Д2, М3, Д3) :-
больше( M2, X),
встав( Д1, X, НД1).
встав( в3( Д1, M2, Д2, М3, Д3), X,
в2( НД1а, Мб, НД1б), M2, в2( Д2, М3, Д3) ) :-
больше( M2, X),
встав( Д1, X, НД1а, Мб, НД1б).
встав( в3( Д1, M2, Д2, М3, Д3), X,
в3( Д1, M2, НД2, М3, Д3) ) :-
больше( X, M2), больше( М3, X),
встав( Д2, X, НД2).
встав( в3( Д1, M2, Д2, М3, Д3), X,
в2( Д1, M2, НД2а), Мб, в2( НД2б, М3, Д3) ) :-
больше( X, M2), больше( М3, X),
встав( Д2, X, НД2а, Мб, НД2б).
встав( в3( Д1, M2, Д2, М3, Д3), X,
в3( Д1, M2, Д2, М3, НД3) ) :-
больше( X, М3),
встав( Д3, X, НД3).
встав( в3( Д1, M2, Д2, М3, Д3), X,
в2( Д1, M2, Д2), М3, в2( НД3а, Мб, НД3б) ) :-
больше( X, М3),
встав( Д3, X, НД3а, Мб, НД3б).
Рис. 10.6. Вставление элемента в 2-3 справочник. В этой программе предусмотрено, что попытка повторного вставления элемента терпит неудачу.
Программа для вставления нового элемента в 2-3 справочник показана полностью на рис. 10.6. На рис. 10.7 показана программа вывода на печать 2-3 деревьев.
Наша программа иногда выполняет лишние возвраты. Так, если встав с тремя аргументами терпит неудачу, то вызывается процедура встав с пятью аргументами, которая часть работы делает повторно. Можно устранить источник неэффективности, если, например, переопределить встав как
встав2( Дер, X, Деревья)
где Деревья — список, состоящий либо из одного, либо из трех аргументов:
Деревья = [ НовДер], если встав( Дер, X, НовДер)
Деревья = [ НДа, Мб, НДб],
если встав( Дер, X, НДа, Мб, НДб)
Теперь отношение доб23 можно переопределить так:
доб23( Д, X, Д1) :-
встав( Д, X, Деревья),
соединить( Деревья, Д1).
Отношение соединить формирует одно дерево Д1 из деревьев, находящихся в списке Деревья.
% Отображение 2-3 справочников
отобр(Д) :-
отобр( Д, 0).
отобр( nil, _ ).
отобр( л(А), H) :-
tab( H), write( A), nl.
отобр( в2( Д1, М, Д2), H) :-
H1 is H + 5,
отобр( Д2, H1),
tab( H), write( --), nl,
tab( H), write( M), nl,
tab( H), write( --), nl,
отобр( Д1, H1).
отобр( в3( Д1, M2, Д2, М3, Д3), H) :-
H1 is H + 5
отобр( Д3, H1),
tab( H), write( --), nl,
tab( H), write( M3), nl,
отобр( Д2, H1),
tab( H), write( M2), nl,
tab( H), write( --), nl,
отобр( Д1, H1).
(a)
15
--
15
--
13
--
13
--
12
--
12
10
10
--
8
--
8
--
7
--
7
--
--
5
--
4
--
