Проектирование систем искусственного интеллекта



         

Представление множеств с помощью бинарных деревьев - часть 2


?- принадлежит_дереву(3000, Т).

Пролог сравнит число 3000 не более чем с 11 элементами множества. прежде чем ответит:

нет

Конечно, если Т имеет линейное представление, то потребуется сравнение 3000 с 1024 элементами множества.

Построение бинарного дерева. Задача создания упорядоченного бинарного дерева при добавлении элемента Х к другому упорядоченному бинарному дереву формулируется следующим образом.

Граничное условие:

Добавление Х к nil дает бд(nil, Х, nil).

Рекурсивные условия:

При добавлении Х к бд(Лд, К, Пд) нужно рассмотреть два случая, чтобы быть уверенным, что результирующее дерево будет упорядоченным.

  1. Х меньше, чем К. В этом случае нужно добавить Х к Лд, чтобы получить левое поддерево. Правое поддерево равно Пд, а значение корня результирующего дерева равно К.
  2. Х больше, чем К. В таком случае нужно добавить Х к Пд, чтобы получить правое поддерево. Левое поддерево равно Лд, а значение корня — К.

Такой формулировке задачи соответствует программа:

/* Граничное условие: включ_бд(nil, Х, бд(nil, Х, nil)). /* Рекурсивные условия: /*(1) включ_бд(бд(Лд, К, Пд), Х, бд(Лднов, К, Пд)) :- Х@К, включ_бд(Лд,Х,Лднов). /*(2) включ_бд(бд(Лд, К, Пд), Х, бд(Лд, К, Пднов)) :- Х@К, включ_бд(Пд, Х, Пднов). На запрос ?- включ_бд(nil, d, Т1), включ_бд(Т1, а, Т2). будут получены значения Т1=бд(nil, d, nil) Т2=бд(бд(nil, а, nil), d, nil)

Процедуру включ_бд() можно использовать для построения упорядоченного дерева из списка:

/* Граничное условие: список_в_дерево([], nil). /* Рекурсивное условие: список_в_дерево([Н | Т], Бд) :- список_в_дерево(Т, Бд2), включ_бд(Н, Бд2, Бд).

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




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