Пример. Далее логично заняться предикатом, который будет удалять заданное значение из двоичного справочника . У него будет три параметра. Два входных (удаляемое значение и исходное дерево ) и результат удаления первого параметра из второго.

Реализовать этот предикат оказывается не так просто, как хотелось бы. Без особых проблем можно написать базисы рекурсии для случая, когда удаляемое значение является корневым, а левое или правое поддерево пусты. В этом случае результатом будет, соответственно, правое или левое поддерево. Шаг рекурсии для случая, когда значение, содержащееся в корне дерева , отличается от удаляемого значения, также реализуется без проблем. Нам нужно выяснить, меньше удаляемое значение корневого или больше. В первом случае перейти к удалению данного значения из левого поддерева, во втором - к удалению этого значения из правого поддерева. Проблема возникает, когда нам нужно удалить корневую вершину в дереве , у которого и левое, и правое поддеревья не пусты.

Есть несколько вариантов разрешения возникшей проблемы. Один из них заключается в следующем. Можно удалить из правого поддерева минимальный элемент (или из левого дерева максимальный) и заменить им значение, находящееся в корне . Так как любой элемент правого поддерева больше любого элемента левого поддерева, дерево , получившееся в результате такого удаления и замены корневого значения, останется двоичным справочником .

Для удаления из двоичного справочника вершины, содержащей минимальный элемент, нам понадобится отдельный предикат. Его реализация будет состоять из двух предложений. Первое будет задавать базис рекурсии и срабатывать в случае, когда левое поддерево пусто. В этой ситуации минимальным элементом дерева является значение, находящееся в корне , потому что, по определению двоичного справочника , все значения, находящиеся в вершинах правого поддерева, больше значения, находящегося в корневой вершине. И, значит, нам достаточно удалить корень , а результатом будет правое поддерево.

Второе предложение будет задавать шаг рекурсии и выполняться, когда левое поддерево не пусто. В этой ситуации минимальный элемент находится в левом поддереве и его нужно оттуда удалить. Так как минимальное значение нам потребуется, чтобы вставить его в корневую вершину, у этого предиката будет не два аргумента, как можно было бы ожидать, а три. Третий (выходной) аргумент будет нужен нам для возвращения минимального значения.

Запишем оба эти предиката.

Начнем со вспомогательного предиката, удаляющего минимальный элемент двоичного справочника .

tree_del_min(tr(X,empty,R), R, X). 
        /* Если левое поддерево пусто, 
         то минимальный элемент - корень, 
         а дерево без минимального 
         элемента - это правое поддерево.*/
tree_del_min(tr(K,L,R), tr(K,L1,R), X):- 
        tree_del_min(L, L1, X). 
        /* Левое поддерево не пусто, 
         значит, оно содержит минимальное 
         значениевсего дерева, 
         которое нужно удалить */

Основной предикат, выполняющий удаление вершины из дерева , будет выглядеть следующим образом.

tree_delete(X,tr(X,empty,R), R):-!. 
        /* X совпадает с корневым 
         значением исходного дерева, 
          левое поддерево пусто */
tree_delete (X,tr(X,L,empty), L):-!. 
        /* X совпадает с корневым 
         значением исходного дерева,
         правое поддерево пусто */
tree_delete (X,tr(X,L,R), tr(Y,L,R1)):- 
        tree_del_min(R,R1, Y). 
          /* X совпадает с корневым 
            значением исходного 
            дерева, причем ни левое, ни 
            правое поддеревья не пусты */
tree_delete (X,tr(K,L,R), tr(K,L1,R)):-
        X<K,!, 
        tree_delete (X,L,L1). 
          /* X меньше корневого значения 
            дерева */
tree_delete (X,tr(K,L,R), tr(K,L,R1)):-
        tree_delete (X,R,R1). 
          /* X больше корневого значения 
            дерева */

Пример. Создадим предикат, который будет преобразовывать произвольный список в двоичный справочник . Предикат будет иметь два аргумента. Первый (входной) - произвольный список, второй (выходной) - двоичный справочник , построенный из элементов первого аргумента.

Будем переводить список в дерево рекурсивно. То, что из элементов пустого списка можно построить лишь пустое дерево , даст нам базис рекурсии. Шаг рекурсии будет основан на той идее, что для того, чтобы перевести непустой список в дерево , нужно перевести в дерево его хвост, после чего вставить голову в полученное дерево .

То же самое на Прологе:

list_tree([],empty). /* Пустому списку 
         соответствует пустое дерево */ 
list_tree([H|T],Tr):-
        list_tree(T,Tr1), 
          /* Tr1 - дерево, построенное 
            из элементов хвоста 
            исходного списка */
        tree_insert(H,Tr1,Tr). 
          /* Tr - дерево, полученное 
            в результате вставки 
            головы списка в дерево Tr1 */

Пример. Создадим обратный предикат, который будет "сворачивать" двоичный справочник в список с сохранением порядка элементов. Предикат будет иметь два аргумента. Первый (входной) - произвольный двоичный справочник , второй (выходной) - список, построенный из элементов первого аргумента.

tree_list(empty,[]). /* Пустому дереву 
         соответствует пустой список */
tree_list(tr(K,L,R),S):-
        tree_list(L,T_L), 
           /* T_L - список, 
            построенный из элементов 
            левого поддерева */
        tree_list(R,T_R), 
           /* T_L - список, 
            построенный из элементов 
            правого поддерева */
        conc(T_L,[K|T_R],S). 
           /* S - список, полученный 
            соединением списков T_L 
            и [K|T_R] */

Заметьте, что, используя предикаты list_tree и tree_list, можно отсортировать список, состоящий из различных элементов, переписав его в двоичный справочник , а затем переписав двоичный справочник обратно в список.

Запишем предикат, выполняющий сортировку списка, переписывая его в двоичный список и обратно.

sort_listT(L,L_S):-
      list_tree(L,T), 
        /* T- двоичный справочник, 
         построенный из элементов 
         исходного списка L */
      tree_list(T,L_S). 
        /* L_S - список, построенный из 
         элементов  двоичного 
         справочника T */

Так как в двоичном справочнике все элементы различны, при переписывании списка в двоичный справочник и обратно повторяющиеся элементы будут из него удалены. Неизменным останется количество элементов списка, только если все его элементы были различны.