Иван Братко - Программирование на языке Пролог для искусственного интеллекта

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

Случай b

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

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

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

Случай с

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

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

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

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

Рис. 10.5.Некоторые из случаев работы отношения встав . (a) встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) ); (b) встав( в2( Д1, М, Д2), X, в3( НД1а, Мб, НД1б, М, Д2) ); (c) встав( в3( Д1, M2, Д2, М3, Д3), X, в2( НД1а, Мб, НД1б), M2, в2( Д2, М3, Д3) ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

встав( в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

--

4

3

3

--

1

AVL-дерево — это дерево, обладающее следующими свойствами: