Prolog

л( Х) представляет дерево, состоящее из одной вершины - листа с элементом X;

в2( Д1, М, Д2) представляет дерево с двумя поддеревьями Д1 и Д2; М - минимальный элемент из Д2;

в3( Д1, М2, Д2, М3, Д3) представляет дерево с тремя поддеревьями Д1, Д2 и Д3; М2 - минимальный элемент из Д2; М3 - минимальный элемент из Д3; Д1, Д2 и Д3 - 2-3 деревья.

Между доб23 и встав существует следующая связь: если после вставления нового элемента дерево не "вырастает", то

        доб23( Дер, X, НовДер) :-

                встав( Дер, X, НовДер).

Однако если после вставления элемента глубина дерева увеличивается, то встав порождает два поддерева Д1 и Д2, а затем составляет из них дерево большей глубины:

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

                встав( Дер, X, Д1, М, Д2).

Отношение встав устроено более сложным образом, поскольку ему приходится иметь дело со многими случаями, а именно вставление в пустое дерево, в дерево, состоящее из одного листа, и в деревья типов  в2  и  в3.   Возникают также дополнительные подслучаи, так как новый элемент можно вставить в первое, либо во второе, либо в третье поддерево. В связи с этим мы определим встав как набор правил таким образом, чтобы каждое предложение процедуры встав имело дело с одним из этих случаев. На рис. 10.5 показаны некоторые из возможных случаев. На Пролог они транслируются следующим образом:

Случай а

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

                больше( М, X),                 % М больше, чем Х

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

Случай b

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

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

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

Случай с

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

                больше( М2, 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, М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),