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


         

Образовавшаяся при этом новая вершина


Образовавшаяся при этом новая вершина передается вверх по дереву для присоединения к одной из выше расположенных вершин. Если же эта ситуация возникает на самом высоком уровне, то дерево вынуждено "вырасти" на один уровень вверх. Рис. 10.3 иллюстрирует описанный принцип.



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

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

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

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

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

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

Здесь НовДер - результат вставления элемента Х в Дер. Деревья Дер

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

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

Имеется в виду, что при вставления Х в Дер

дерево Дер разбивается на два дерева НДа

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



Рис. 10. 4.  Объекты, показанные на рисунке, удовлетворяют отношению встав( Дер, 6, НДа, Мб, НДб).

2-3 деревья мы будем представлять в программе следующим образом:

  • nil представляет пустое дерево;


  • л( Х) представляет дерево, состоящее из одной вершины - листа с элементом X;


  • в2( Д1, М, Д2) представляет дерево с двумя поддеревьями Д1 и Д2; М - минимальный элемент из Д2;


  • в3( Д1, М2, Д2, М3, Д3) представляет дерево с тремя поддеревьями Д1, Д2 и Д3; М2 - минимальный элемент из Д2; М3 - минимальный элемент из Д3; Д1, Д2 и Д3 - 2-3 деревья.


  • Между доб23 и встав

    существует следующая связь: если после вставления нового элемента дерево не "вырастает", то


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