соединить( Д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, Нс),
