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



         

Представление множеств двоичными деревьями - часть 4


Общий метод поиска в двоичном справочнике состоит в следующем:

line();

Для того, чтобы найти элемент Х в справочнике Д, необходимо:

  • если Х - это корень справочника Д, то считать, что Х уже найден, иначе
  • если Х меньше, чем корень, то искать Х в левом поддереве, иначе
  • искать Х в правом поддереве;
  • если справочник Д пуст, то поиск терпит неудачу.
  • line();

    Эти правила запрограммированы в виде процедуры, показанной на рис. 9.7. Отношение больше( X, Y), означает, что Х больше, чем Y. Если элементы, хранимые в дереве, - это числа, то под "больше, чем" имеется в виду просто Х > Y.

    Существует способ использовать процедуру внутри

    также и для построения двоичного справочника. Например, справочник Д, содержащий элементы 5, 3, 8, будет построен при помощи следующей последовательности целей:

            ?-  внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).

            Д = дер( дер( Д1, 3, Д2), 5, дер( Д3, 8, Д4) ).

    Переменные Д1, Д2, Д3 и Д4 соответствуют четырем неопределенным поддеревьям. Какими бы они ни были, все равно дерево Д будет содержать заданные элементы 3, 5 и 8. Структура построенного дерева зависит от того порядка, в котором указываются цели (рис. 9.8).

    line();

            внутри( X, дер( _, X, _ ).

            внутри( X, дер( Лев, Корень, Прав) ) :-

                    больше( Корень, X),

                  % Корень больше, чем Х

                    внутри( X, Лев).

                        % Поиск в левом поддереве

            внутри( X, дер( Лев, Корень, Прав) ) :-

                    больше( X, Корень),




    Содержание  Назад  Вперед