M нз Н2

Рис. 10.7. Три правила формирования AVL-дерсвьсв

Последний параметр, NewTree, представляет собой AVL-дерево, сформированное из пяти компонентов, которые заданы первыми пятью параметрами. Например, пра­вило 1 принимает следующий вид:

combine(

Tl/HI, A, t(T21_fB,T22) / Н2, С, ТЗ/НЗ, % Пять компонентов

t(t(Tl/Hl,A, Т21)/На, В, t (T22, С, ТЗ/НЗ) /Не) /НЬ):- % Кх сочетание

Н2 > HI, H2 > НЗ, % Среднее дерево - самое высокое

На is Hi + 1, % Высота левого поддерева

НС is НЗ + i, I Высота правого поддерева

НЬ is На + 1. % Высота всего дерева

Полная версия программы addavl, которая вычисляет также значения высоты дерева и поддеревьев, приведена в листинге 10.3.

Глава 10. Усовершенствованные методы представления деревьев

Листинг 10.3. Программа вставки в AVL-словарь;. в этой программе попытка вставки дублирующегося элемента оканчивается неудачей (определение отношения combine см. на рис. 10.7)

% addavl-! Tree, X, NewTree): вставка Б AVL-словарь

% Tree = t(Left, Root, Kight)/KeightOfTree

% Пустое дерево - nil/0

addavl(nil/0, X, t(nil/0,X,nil/0)/1). % Ввести элемент X в пустое дерево

addavl (t (L, Y, Р.)/Ну, X, NewTree}:- % Ввести элемент Х в непустое дерево

gtf y, X),

addavl(L, X, t(Li,Z,L2)/_), Щ Ввести элемент Х в левое поддерево

combine (LI, Z, L2, Y, R, NewTree). % Объединить компоненты дерева НеыТгее

addavl (t(L,Y,R)/Hy, X, NewTree):-gt |X, Y),

addavl(R, X, t(Rl,Z,R2)/_), % Ввести E правое поддерево

combine; L, Y, Rl, Z, R2, NewTree).

^ combine(Treel, A, Tree2, В, ТгееЗ, NewTree):

% Объединить поддеревья Treel, Tree2, ТгееЗ и узлы А и В в AVL-дерево combine! Tl/Hl, A, t(Т21,В,Т22)/Н2, С, ТЗ/НЗ,

t[ t(Tl/Hl,A,T21)/На, В, t(T22,С,ТЗ/НЗ)/Не)/НЬ):-

Н2 > HI _л H2 > НЗ, % Среднее поддерево - самое высокое

На is HI + 1, НС is НЗ + 1, НЬ is На + 1.

combine! Tl/Hl, A, T2/H2, С, ТЗ/НЗ,

t(Tl/Hl, A, t(Т2/Н2,С,ТЗ/НЗ)/Нс)/На i:-
HI >= Н2, HI > = НЗ, % Высокое левое поддерево

max! (Н2, НЗ, Не!, maxl(HI, He, На).

combine! Tl/Hl, A, T2/H2, С, ТЗ/НЗ,

t(t[Tl/Hl,A,T2/H2)/Ha, С, ТЗ/НЗ}/НС):-
НЗ >«Н2, 113 >- HI, h Высокое правое поддерево

maxl (HI, H2, На), аахК На, НЗ, не).

raaxl [ U, V, М):- % И равно 1 + максимальное иэ двух значение, F и V

U > V,!, И is и + 1; И is V + 1,

В процессе работы этой программы учитываются значения высоты деревьев. Но, как было указано выше, возможен более краткий способ представления. В действи­тельности необходимо знать лишь степень нарушения сбалансированности (разницу высот), которая может составлять только -1,0 или +1. Тем не менее недостатком та­кого сокращенного способа представления является некоторое усложнение правил соединения компонентов.

Упражнения

10.3. Определите отношение avi(Tree)

для проверки того, является ли AVL-деревом бинарное дерево Tree; это озна­чает, что все поддеревья одного уровня могут отличаться друг от друга по вы­соте ае больше чем на 1. Допустим, что бинарные деревья представлены с по­мощью термов в форме t { Left, Root, Right) или nil.

Часть!. Язык Prolog

10.4. Проведите трассировку выполнения алгоритма вставки в AVL-дерево, начиная с пустого дерева и последовательно вставляя элементы 5, 8, 9, 3, 1, 6, 7. Как изменяется корневой элемент во время этого процесса?

Резюме

• Двоично троичные иAVL-деревья, рассматриваемые в данной главе, относятся

к разновидностям сбалансированных деревьев.

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