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

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

Запишем на Прологе реализацию этих рассуждений.

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

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

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

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

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

Решение будет, естественно, рекурсивным. Рекурсия по количеству вершин дерева . Базис рекурсии: нулевое количество вершин имеется только в пустом дереве . Если количество вершин должно быть больше нуля, то нужно (с помощью встроенного предиката random, рассмотренного в пятой лекции) сгенерировать случайное значение, построить дерево , имеющее вершин на одну меньше, чем итоговое дерево , вставить случайное значение в построенное дерево , воспользовавшись созданным перед этим предикатом tree_insert.

tree_gen(0,empty):-!. /* ноль вершин 
         соответствует пустому дереву */ 
tree_gen (N,T):-
       random(100,X), 
          /* X - случайное число 
            из промежутка [0,100) */
       N1= N-1,
       tree_gen (N1,T1), 
          /* T1 - дерево, имеющее 
            N-1 вершин */
       tree_insert(X,T1,T). /* вставляем X 
                 в дерево T1 */

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

Если нам обязательно нужно по какой-то причине получить дерево , содержащее ровно столько вершин, сколько было указано в первом параметре, нужно модифицировать этот предикат. Это можно сделать несколькими способами.

Первый вариант: можно модифицировать предикат, осуществляющий добавление значения в двоичный справочник так, чтобы в случае, когда вставляемое значение совпадало с корневым значением, генерировалось новое случайное число, после чего еще раз осуществлялась попытка вставки вновь сгенерированного значения в дерево .

Другой вариант: можно поменять местами вызов предикатов random и tree_gen и после генерации случайного числа проверять с помощью предиката tree_member2, не содержится ли это значение в уже построенном дереве . Если его там нет, значит, его можно спокойно вставить в двоичный справочник с помощью предиката tree_insert. Если же это значение уже содержится в одной из вершин дерева , значит, нужно сгенерировать новое случайное число, после чего опять проверить его наличие и т.д.

Надо заметить, что если задать требуемое количество вершин дерева , заведомо большее, чем первый аргумент предиката random (количество различных случайных чисел, генерируемых этим предикатом), мы получим зацикливание. Например, в приведенном выше примере вызывается предикат random(100,X). Этот предикат будет возвращать целые случайные числа из промежутка от 0 до 99. Различных чисел из этого промежутка всего сто. Следовательно, и справочник , генерируемый с помощью нашего предиката, может содержать не более ста вершин.

Эту проблему можно обойти, если сделать первый аргумент предиката random зависящим от заказанного числа вершин дерева (заведомо больше).