Основы проектирования систем искусственного интеллекта



         

ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ С ПОМОЩЬЮ БИНАРНЫХ ДЕРЕВЬЕВ - часть 2


/* поддереве:

принадлсжит_дереву(Х, бд(Лд, У, Пд)) :- X@Y,

припадлежит_дереву(Х, Пд).

/* Х принадлежит дереву, если Х меньше

/* значения корня и находится в левом

/* поддереве:

принадлежит_дереву(Х, бд(Лд ,У ,Пд)) :-X@Y,

принадлежит_дереву(Х, Лд).

Если множество из первых 1024 чисел описать с помощью сба­лансированного бинарного дерева Т, то при ответе на запрос

?- принадлежит_дереву(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, Бд).

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




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