Функционально-логическое программирование. Лабораторная работа 3.

8-rbt.pl

% балансировка красно-чёрного поддерева
% (объясняется графически)
balance(T,tr(red,B,tr(black,A,T1,T2),tr(black,C,T3,T4))) :-
    T=tr(black,A,T1,tr(red,B,T2,tr(red,C,T3,T4))),!;
    T=tr(black,C,tr(red,B,tr(red,A,T1,T2),T3,T4)),!;
    T=tr(black,A,T1,tr(red,C,tr(red,B,T2,T3),T4)),!;
    T=tr(black,C,tr(red,A,T1,tr(red,B,T2,T3)),T4),!.
balance(T,T).

% вставка узла в красно-чёрное дерево
% (не гарантирует черноту корня)
ins(e,X,tr(red,X,e,e)).
ins(tr(C,X,L,R),X,tr(C,X,L,R)).
ins(tr(C,Y,L,R),X,Res) :-
    X<Y,ins(L,X,L1),balance(tr(C,Y,L1,R),Res);
    X>Y,ins(R,X,R1),balance(tr(C,Y,L,R1),Res).

% принудительное окрашивание в чёрный цвет
% (не нарушает правил красно-чёрного дерева)
blackenize(tr(_,X,L,R),tr(black,X,L,R)).

% добавление узла, состоит из:
% - вставки
% - и окрашивания корня в чёрный цвет
add(T,X,Res) :- ins(T,X,T1),blackenize(T1,Res).

% самостоятельное задание:
% - последовательно добавить в пустое дерево элементы от 1 до 1000
% - подсчитать глубину дерева