Prolog

Неизвестно

(a) встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) );

(b) встав( в2( Д1, М, Д2), X,

в3( НД1а, Мб, НД1б, М, Д2) );

(c) встав( в3( Д1, М2, Д2, М3, Д3), X,

в2( НД1а, Мб, НД1б), М2, в2( Д2, М3, Д3) ).

%

Вставление элемента в 2-3 справочник

доб23( Дер, X, Дер1) :- % Вставить Х в Дер, получить Дер1

встав( Дер, X, Дер1). % Дерево растет вширь

доб23( Дер, X, в2( Д1, М2, Д2) ) :-

встав( Дер, X, Д1, М2, Д2). % Дерево растет вглубь

доб23( nil, X, л( Х) ).

встав( л( А), X, л( А), X, л( Х) ) :-

больше( X, А).

встав( л( А), X, л( Х), А, л( А) ) :-

больше( А, X).

встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) ) :-

больше( М, X),

встав( Д1, X, НД1).

встав( в2( Д1, М, Д2), Х, в3( НД1а, Мб, НД1б, М, Д2) ) :-

больше( М, X),

встав( Д1, X, НД1а, Мб, НД1б).

встав( в2( Д1, М, Д2), X, в2( Д1, М, НД2) ) :-

больше( X, М),

встав( Д2, X, НД2).

встав( в2( Д1, М, Д2), Х, в3( Д1, М, НД2а, Мб, НД2б) ) :-

больше( X, М),

встав( Д2, X, НД2а, Мб, НД2б).

встав( в3( Д1, М2, Д2, М3, Д3), Х, в3( НД1, М2, Д2, М3, Д3) :-

больше( М2, X),

встав( Д1, X, НД1).

встав( в3( Д1, М2, Д2, М3, Д3), X,

в2( НД1а, Мб, НД1б), М2, в2( Д2, М3, Д3) ) :-

больше( М2, X),

встав( Д1, X, НД1а, Мб, НД1б).

встав( в3( Д1, М2, Д2, М3, Д3), X,

в3( Д1, М2, НД2, М3, Д3) ) :-

больше( X, М2), больше( М3, X),

встав( Д2, X, НД2).

встав( в3( Д1, М2, Д2, М3, Д3), X,

в2( Д1, М2, НД2а), Мб, в2( НД2б, М3, Д3) ) :-

больше( X, М2), больше( М3, X),

встав( Д2, X, НД2а, Мб, НД2б).

встав( в3( Д1, М2, Д2, М3, Д3), X,

в3( Д1, М2, Д2, М3, НД3) ) :-

больше( X, М3),

встав( Д3, X, НД3).

встав( в3( Д1, М2, Д2, М3, Д3), X,

в2( Д1, М2, Д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 из деревьев, находящихся в списке Деревья.