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



         

Двоично - троичные справочники - часть 3


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

fig10_3.gif (2453 bytes)

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

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

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

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

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

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

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

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

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

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

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

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

fig10_4.gif (1762 bytes)

Рис. 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 и встав

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




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