Упражнение. 10.3. Определите отношение

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

avl(Дер)

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

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

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

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

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

% Добавить 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.

Резюме

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

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

Литература

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

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

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

Aho А. V., Hopcroft J. E. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.

Gonnet G. H. (1984). Handbook of Algorithms + Data Structures. Addison-Wesley.

van Emden M. (1981). Logic Programming Newsletter 2.

Wirth N. (1976). Algorithms + Data Structures = Programs. Prentice-Hall. [Имеется перевод: Вирт H. Алгоритмы + структуры данных = программы. — M.: Мир, 1985.]