M нз Н2
Рис. 10.7. Три правила формирования AVL-дерсвьсв
Последний параметр, NewTree, представляет собой AVL-дерево, сформированное из пяти компонентов, которые заданы первыми пятью параметрами. Например, правило 1 принимает следующий вид:
combine(
Tl/HI, A, t(T21fB,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, где п — количество узлов в дереве.