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


         

в R, поэтому имеем следующее


Теперь рассмотрим вставление элемента Х в непустой AVL-справочник

        Дер = д( L, A, R)/H

Начнем со случая, когда Х больше А. Х необходимо вставить в R, поэтому имеем следующее отношение:

        доб_аv1( R, X, д( R1, В, R2)/Hb)

На рис. 10.8 показаны составные части, из которых строится дерево НовДер:

        L, А, R1, В, R2

Какова глубина деревьев L, R, R1 и R2?  L и R могут отличаться по глубине не более, чем на 1. На рис. 10.8 видно, какую глубину могут иметь R1 и R2. Поскольку в R был добавлен только один элемент X, только одно из поддеревьев R1, R2 может иметь



Рис. 10. 9.  Три правила построения нового AVL-дepевa.

глубину h +1.

В случае, когда Х меньше, чем А, имеем аналогичную ситуацию, причем левое и правое поддеревья меняются местами. Таким образом, в любом случае мы должны построить дерево НовДер, используя три дерева (назовем их Дер1, Дер2

и Дер3) и два отдельных элемента А и В. Теперь рассмотрим вопрос: как соединить между собой эти пять составных частей, чтобы дерево НовДер

было AVL-справочником? Ясно, что они должны располагаться внутри НовДер в следующем порядке (слева направо):

        Дер1, А, Дер2, В, Дер3

Рассмотрим три случая:

(1)        Среднее дерево Дер2

глубже остальных двух деревьев.

(2)        Дер1 имеет глубину не меньше, чем Дер2 и Дер3.

(3)        Дер3 имеет глубину не меньше, чем Дер2 и Дер1.

На рис. 10.9 видно, как можно построить дерево НовДер

в каждом из этих трех случаев. Например, в случае 1 среднее дерево Дер2 следует разбить на два части, а затем включить их в состав НовДер. Три правила, показанные на pис.10.9, нетрудно запасать на Прологе в виде отношения

        соединить( Дер, А, Дер2, В, Дер3, НовДер)

Последний аргумент НовДер - это AVL-дерево, построенное из пяти составных частей, пяти первых аргументов.

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