Форум программистов [Powered by Invision Power Board]

Код


insert_leaf(X, empty, tree(X, empty, empty)).
insert_leaf(X, tree (Y, L, R), tree(Y, L1, R)):-
        X < Y,!,insert_leaf(X, L, L1).
insert_leaf(X, tree(Y, L, R), tree(Y, L, R1)):-
        X > Y,!,insert_leaf(X, R, R1).

Цитата(blur @ 28.4.2007, 20:16

)

дерево получается хоть и упорядоченное, но не бинарное (если ввести 1,2,3, то получается 1-корень,2-правое,3-правое, а надо 2-корень, 1-левое, 3-правое). Помогите пожалуйста модифицировать данный предикат.

Цитата

?- insert_leaf(1,empty,X),insert_leaf(2,X,Y),insert_leaf(3,Y,Z).

X = tree(1, empty, empty)
Y = tree(1, empty, tree(2, empty, empty))
Z = tree(1, empty, tree(2, empty, tree(3, empty, empty)))

Yes
?- insert_leaf(3,empty,X),insert_leaf(2,X,Y),insert_leaf(1,Y,Z).

X = tree(3, empty, empty)
Y = tree(3, tree(2, empty, empty), empty)
Z = tree(3, tree(2, tree(1, empty, empty), empty), empty)

Yes
?- insert_leaf(2,empty,X),insert_leaf(3,X,Y),insert_leaf(1,Y,Z).

X = tree(2, empty, empty)
Y = tree(2, empty, tree(3, empty, empty))
Z = tree(2, tree(1, empty, empty), tree(3, empty, empty))

Yes
?-

Цитата(Artemios @ 29.4.2007, 16:10

)

Вообще, в сети много про них пишут. Посмотри, если не будет получаться -- пиши.

Код


% Дерево представляем в виде: 
% tr(Корень,ЛевоеПоддерево,ПравоеПоддерево,ВысотаДерева)

% вставка в упорядоченное дерево
ins(X,nil,tr(X,nil,nil,1)).
ins(X,tr(Y,L,R,H),tr(Y,L2,R,H2)):-
    X<Y, H2 is H+1, ins(X,L,L2).
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<Hl,
        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
?-

Цитата(blur @ 30.4.2007, 01:44

)

Так что не мог бы ты мне написать нужный предикат - лабу скоро нужно сдавать smile

Цитата(Artemios @ 1.5.2007, 00:07

)

С тебя пиво smile Много smile

Цитата(blur @ 1.5.2007, 01:14)

А вот пиво только таким образом smile