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

       

Три правила построения нового AVLдepевa



Рисунок 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-дерево, построенное из пяти составных частей, пяти первых аргументов. Правило 1, например, принимает вид:

        соединить( Д1/Н1, А, д( Д21, В, Д22)/Н2, С, Д3/Н3,
                                                                    % Пять частей
        д( д( Д1/Н1, А, Д21)/На, В, д( Д22, С, Д3/Н3)/Нс)/Нb) :-
                                                                    % Результат
                H2 > H1, H2 > Н3,                     % Среднее дерево глубже остальных
                На is Н1 + 1,                              % Глубина левого поддерева
                Нс is Н3 + 1,                              % Глубина правого поддерева
                Hb is На + 1,                              % Глубина всего дерева

Программа доб_аvl, вычисляющая также глубину дерева и его поддеревьев, показана полностью на Рисунок 10.10.



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