. 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, .
