Prolog

На рис. 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.

Упражнение

10. 3.    Определите отношение

        avl( Дер)

для проверки того, является ли Дер AVL-деревом, т.е. верно ли, что любые два его поддерева, подсоединенные к одной и той же вершине, отличаются по глубине не более чем на 1. Двоичные

%  Вставление элемента в AVL-справочник

        доб_аvl( nil/0, X, д( nil/0, X, nil/0)/1).

                                    % Добавить Х к пустому дереву

        доб_аvl( д( L, Y, R)/Ну, X, НовДер) :-

                                    % Добавить Х к непустому дереву

                больше( Y, X),

                доб_аvl( L, X, д( L1, Z, L2)/ _ ),

                                    % Добавить к левому поддереву

                соединить( L1, Z, L2, Y, R, НовДер).

                                    % Сформировать новое дерево

        доб_avl( д( L, Y, R)/Ну, X, НовДер) :-

                больше( X, Y),

                доб_avl( R, X, д( R1, Z, R2)/ _ ),

                                    % Добавить к правому поддереву

                соединить( L1, Y, Rl, Z, R2, НовДер).

        соединить( Д1/Н1, А, д( Д21, В, Д22)/Н2, С, Д3/Н3,

                д( д( Д1/Н1, А, Д21)/На, В, д( Д22, С, L3/Н3)/Нс)/Нb) :-

                Н2 > H1, H2 > Н3,                 % Среднее дерево глубже остальных

                На is H1 + 1,

                Hс is Н3 + 1,

                Нb is На + 1.

        соединить( Д1/Н1, А, д( Д2/Н2, С, Д3/Н3,

                д( Д1/Н1, А, д( Д2/Н2, С, Д3/Н3)/Нс)/На) :-

                H1 >= H2, H1 >= Н3,            % "Глубокое" левое дерево

                max1( H2, Н3, Нс),

                max1( H1, Нс, На).

        соединить( Д1/Н1, А, Д2/Н2, С, Д3/Н3,

                д( д( Д1/Н1, А, Д2/Н2)/На, С, Д3/Н3)/Нс) :-

                Н3 >= H2, Н3 >= H1,            % "Глубокое" правое дерево

                max1( H1, H2, На),

                max1( На, Н3, Нс).

        max1( U, V, М) :-

                U > V,  !,  М is U + 1;            % М равно 1 плюс max( U,V)

                М is V + 1.

Рис. 10. 10.  Вставление элемента в AVL-справочник. В этой

программе предусмотрено, что попытка повторного вставления

элемента терпит неудачу. По поводу процедуры соединить см.

рис. 10.9.

деревья представляйте в виде термов

        д( Лев, Кор, Прав) или nil.

Посмотреть ответ

Резюме

2-3 деревья и AVL-деревья, представленные в настоящей главе, - это примеры сбалансированных деревьев.

Сбалансированные или приближенно сбалансированные деревья гарантируют эффективное выполнение трех основных операций над деревьями: поиск, добавление и удаление элемента. Время выполнения этих операций пропорционально log n, где n - число вершин дерева.

Литература

2-3 деревья детально описаны, например, в Aho, Hopcroft and Ullman (1974, 1983). В книге этих авторов, вышедшей в 1983 г., дается также реализация соответствующих алгоритмов на языке Паскаль. Н.Вирт (см. Wirth (1976)) приводит программу на Паскале для работы с AVL-деревьями. 2-3 деревья являются частным случаем более общего понятия В-деревьев. В-деревья, а также несколько других вариантов структур данных, имеющих отношение к 2-3 деревьям в AVL-деревьям, рассматриваются в книге Gonnet (1984). В этой книге, кроме того, даны результаты анализа поведения этих структур.

Программа вставления элемента в AVL-дерево, использующая только величину "перекоса" дерева (т.е. значение разности глубин поддеревьев, равной -1, 0 или 1, вместо самой глубины) опубликована ван Эмденом (1981).

Aho А. V., Hopcroft J. Е. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. - М.: Мир, 1979.]