Prolog

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

Упражнения

10. 1.    Определите отношение

        внутри( Эдем, Дер)

для поиска элемента Элем в 2-3 справочнике Дер.

Посмотреть ответ

10. 2.    Введите в программу рис. 10.6 изменения для устранения лишних возвратов (определите отношения встав2 и соединить).

%  Отображение 2-3 справочников

        отобр(Д) :-                                                                                                         15

            отобр( Д, 0).                                                                                             --

        отобр( nil, _ ).                                                                                            15

        отобр( л(А), Н) :-                                                                                        --

                tab( H), write( A), nl.                                                                               13

        отобр( в2( Д1, М, Д2), Н) :-                                                                  --

                H1 is H + 5                                                                                       13

                отобр( Д2, H1),                                                                               --

                tab( H), write( --), nl,                                                                               12

                tab( H), write( M), nl,                                                                           --

                tab( H), write( --), nl,                                                                         12

                отобр( Д1, H1).                                                                                         10

        отобр( в3( Д1, M2, Д2, М3, Д3), H) :-                                                        10

                H1 is H + 5                                                                                             --

                отобр( Д3, H1),                                                                                          8