Дерево представляем в виде:
tr(Корень,ЛевоеПоддерево,ПравоеПоддерево,ВысотаДерева)
% вставка в упорядоченное дерево
ins(X,nil,tr(X,nil,nil,1)).
ins(X,tr(Y,L,R,H),tr(Y,L2,R,H2)):-
X
ins(X,tr(Y,L,R,H),tr(Y,L,R2,H2)):-
X>Y, H2 is H+1, ins(X,R,R2).
height(nil,0).
height(tr(_,_,_,H),H).
% малое правое вращение
rot_right_small(
tr(A,L,tr(B,C,R,_),_),
tr(B,tr(A,L,C,Ha2),R,Hb2)
):-
height(C,Hc),
height(R,Hr),
Hc < Hr,
height(L,Hl),
Ha2 is max(Hl,Hc)+1,
Hb2 is max(Ha2,Hr)+1.
% большое правое вращение
rot_right_big(
tr(A,L,tr(B,tr(C,M,N,Hc),R,_),_),
tr(C,tr(A,L,M,Ha2),tr(B,N,R,Hb2),Hc2)
):-
height(R,Hr),
Hc>Hr,
height(L,Hl),
height(M,Hm),
height(N,Hn),
Ha2 is max(Hl,Hm)+1,
Hb2 is max(Hn,Hr)+1,
Hc2 is max(Ha2,Hb2)+1.
rot_left_small(
tr(A,tr(B,L,C,_),R,_),
tr(B,L,tr(A,C,R,Ha2),Hb2)
):-
height(C,Hc),
height(L,Hl),
Hc
height(R,Hr),
Ha2 is max(Hc,Hr)+1,
Hb2 is max(Hl,Ha2)+1.
rot_left_big(
tr(A,tr(B,L,tr(C,M,N,Hc),_),R,_),
tr(C,tr(B,L,M,Hb2),tr(A,N,R,Ha2),Hc2)
):-
height(L,Hl),
Hc>Hl,
height(M,Hm),
height(N,Hn),
height(R,Hr),
Ha2 is max(Hn,Hr)+1,
Hb2 is max(Hl,Hm)+1,
Hc2 is max(Ha2,Hb2)+1.
% балансировка
balance(nil,nil,0).
balance(tr(X,L,R,_),tr(X2,L2,R2,H2),H2):-
balance(L,LL,Hl),
balance(R,RR,Hr),
HH is max(Hl,Hr)+1, (
abs(Hl-Hr)<2,
X=X2, L2=LL, R2=RR, H2=HH;
Hr-Hl =:= 2, (
rot_right_small(tr(X,LL,RR,HH),tr(X2,L2,R2,H2));
rot_right_big(tr(X,LL,RR,HH),tr(X2,L2,R2,H2))
);
Hl-Hr =:= 2, (
rot_left_small(tr(X,LL,RR,HH),tr(X2,L2,R2,H2));
rot_left_big(tr(X,LL,RR,HH),tr(X2,L2,R2,H2))
)
).
% вставка в АВЛ-дерево
avl_insert(X,Tree,TreeNew):-
ins(X,Tree,T),
balance(T,TreeNew,_).
list2avl([],T,T).
list2avl([X|Xs],T,T2):-
avl_insert(X,T,TT),
list2avl(Xs,TT,T2).
list2avl(Lst,Tr):-list2avl(Lst,nil,Tr).
Проверка:
?- list2avl([2,1,6,4,5,3],T).
T = tr(4, tr(2, tr(1, nil, nil, 1), tr(3, nil, nil, 1), 2), tr(5, nil, tr(6, nil, nil, 1), 2), 3)
Yes
?- list2avl([3,1,5,4,2,6],T).
T = tr(3, tr(1, nil, tr(2, nil, nil, 1), 2), tr(5, tr(4, nil, nil, 1), tr(6, nil, nil, 1), 2), 3)
Yes
?- list2avl([1,2,3,4,5,6],T).
T = tr(4, tr(2, tr(1, nil, nil, 1), tr(3, nil, nil, 1), 2), tr(5, nil, tr(6, nil, nil, 1), 2), 3)
Yes
?- list2avl([6,5,4,3,2,1],T).
T = tr(3, tr(2, tr(1, nil, nil, 1), nil, 2), tr(5, tr(4, nil, nil, 1), tr(6, nil, nil, 1), 2), 3)
Yes
?-
|
Главная
Каталог файлов
