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

         

Вставление нового элемента в 2-3 справочник. Дерево



  Вставление нового элемента в 2-3 справочник. Дерево


растет сначала вширь, а затем уже вглубь.

Включение нового элемента в 2-3 справочник мы запрограммируем как отношение

        доб23( Дер, X, НовДер)

где дерево НовДер получено введением элемента Х в дерево Дер. Основную работу мы поручим двум дополнительным отношениям, которые мы назовем встав. Первое из них имеет три аргумента:

        встав( Дер, X, НовДер).

Здесь НовДер - результат вставления элемента Х в Дер. Деревья Дер и НовДер имеют одну и ту же глубину. Разумеется, не всегда возможно сохранить ту же глубину дерева. Поэтому существует еще одно отношение с пятью аргументами специально для этого случая:

        встав( Дер, X, НДа, Mб, НДб).

Имеется в виду, что при вставления Х в Дер дерево Дер разбивается на два дерева НДа и НДб, имеющих ту же глубину, что и Дер. Мб - это минимальный элемент из НДб. Пример показан на рис. 10.4.



Содержание раздела