Прим. кода на этом нечто:
sort_btree(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y).
tree_list(nil, []).
tree_list(tree(X, L, R, _), List) :- tree_list(L, ListL), tree_list(R, ListR),
append(ListL, [X|ListR], List).
sort_tree([], nil).
sort_tree([X|L], Tree) :- sort_tree(L, LTree), plus_tree(X, LTree, Tree).
construct_tree(A, AL, AR, tree(A, AL, AR, ADepth)) :- diff(AL, AR, _, ADepth).
diff(AL, AR, ADiff, ADepth) :- depth_tree(ALs, AL), depth_tree(ARs, AR),
ADiff is ALs - ARs, max_int(ALs, ARs, AD), ADepth is AD + 1.
max_int(A, B, A) :- A > B.
max_int(A, B, B) :- A =< B.
append([], L, L).
append([X|L], R, [X|T]) :- append(L, R, T).
depth_tree(0, nil).
depth_tree(X, tree(_, _, _, X)).
plus_tree(X, nil, tree(X, nil, nil, 1)).
plus_tree(X, tree(O, L, R, _), Res) :- O >= X, plus_tree(X, L, ResL), diff(ResL, R, Diff, Dep),
balance_tree(tree(O, ResL, R, Dep), Diff, Res).
plus_tree(X, tree(O, L, R, _), Res) :- O < X, plus_tree(X, R, ResR), diff(L, ResR, Diff, Dep),
balance_tree(tree(O, L, ResR, Dep), Diff, Res).
%% No rotations
balance_tree(Tree, ADiff, Tree) :- ADiff < 2, ADiff > -2.
%% Small right rotation
balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :-
ADiff > 1, diff(BL, BR, BDiff, _), BDiff >= 0,
construct_tree(A, BR, AR, ASubTree), construct_tree(B, BL, ASubTree, Result).
%% Big right rotation
balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :-
ADiff > 1, diff(BL, BR, BDiff, _), BDiff < 0, BR = tree(C, CL, CR, _),
construct_tree(B, BL, CL, BSubTree), construct_tree(A, CR, AR, ASubTree),
construct_tree(C, BSubTree, ASubTree, Result).
%% Small left rotation
balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :-
ADiff < -1, diff(BL, BR, BDiff, _), BDiff =< 0,
construct_tree(A, AL, BL, ASubTree), construct_tree(B, ASubTree, BR, Result).
%% Big left rotation
balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :-
ADiff < -1, diff(BL, BR, BDiff, _), BDiff > 0, BL = tree(C, CL, CR, _),
construct_tree(B, CR, BR, BSubTree), construct_tree(A, AL, CL, ASubTree),
construct_tree(C, ASubTree, BSubTree, Result).