Rooted Binary Trees in Prolog
Root-to-leaf paths, Depth of a Rooted Binary Tree, Tree Rotation, Root-Balancing, Root-Balancing Tree Sort
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rooted Binary Trees in Prolog:
% Root-to-leaf paths, Depth of a Rooted Binary Tree, Tree Rotation, Root-Balancing, Root-Balancing Tree Sort
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nicolaie Popescu-Bodorin, 2009
% http://fmi.spiruharet.ro/bodorin/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prolog, TP 2.0
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rooted Binary Trees (RBT)
CONSTANTS
t1 = t(4,t(3,t(8,t(1,e,e),e),t(0,t(2,e,e),t(2,e,t(3,e,t(5,e,e))))),t(5,e,t(1,t(4,e,e),t(3,t(5,e,e),t(2,e,e))))) % a tree for running the tests.
% t1 is not FULL:
% ________4________
% ____3____ 5______
% __8 __0__ ____1____
% 1 2 2__ 4 __3__
% 3__ 5 2
% 5
%
l1=[4,3,5,8,0,1,1,2,2,4,3,3,5,2,5]
l2=[9,8,7,6,5,4,3,2,1,0,9,8,7,6,5,4,3,2,1,0]
l3=[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2]
l4=[9,5,6,2,1,4,3,5,4,7,6,2,4,8,7,3,6,0,6,2] %rnd
l5=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
l6=[0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9]
l7=[1,2,3,2,3,4,3,4,5,4,5,6,5,6,7,6,7,8,7,8]
l8=[0,9,1,8,2,7,3,6,4,5,5,4,6,3,7,2,8,1,9,0]
% 40 rnd elements:
l9=[5,8,2,9,3,0,6,9,3,5,2,7,4,9,6,1,4,2,7,5,4,8,2,7,2,8,1,6,3,8,4,0,5,7,2,8,4,8,5,1]
t2 = t( 4, t(3,t(8,t(1,e,e),t(4,e,e)),t(0,t(2,e,e),t(2,t(1,e,e),t(3,t(8,e,e),t(5,e,e))))), t(5,t(2,e,e),t(1,t(4,e,e),t(3,t(5,e,e),t(2,e,e)))) )
% t2 is FULL but not PERFECT:
% _________4_________
% _____3_____ ____5______
% __8__ ___0___ 2 ____1____
% 1 4 2 __2__ 4 __3__
% 1 __3__ 5 2
% 8 5
%
t3 = t( 4, t(3,t(8,t(1,e,e),t(4,e,e)),t(0,t(2,e,e),t(2,e,e))), t(5,t(2,t(0,e,e),t(8,e,e)),t(1,t(4,e,e),t(3,e,e))) )
% t3 is PERFECT (hence, it is also FULL):
% _________4_________
% _____3_____ _____5_____
% __8__ __0__ __2__ __1__
% 1 4 2 2 0 8 4 3
DOMAINS
r=real
lr=r*
llr=lr*
rbt = t(r,rbt,rbt);e % e stands for an empty (sub-)tree
% A Rooted Binary Tree (RBT) is an empty data structure
% or a recursive data structure in which any node is
% root for at most two rooted binary trees - left and right
% sub-trees, each of them posibly being empty.
PREDICATES
lconcat(lr,lr,lr)
CLAUSES
lconcat([],L,L).
lconcat([H|T],L,[H|TR]):-lconcat(T,L,TR).
/******** INORDER traversal (reading) of a tree ***/
% inoder/infix/symetric/srd/lRr traversal
PREDICATES
inorder(rbt,lr)
CLAUSES
inorder(e,[]):-!.
inorder(t(X,L,R),TL):-
inorder(L,LL),
inorder(R,RL),
lconcat(LL,[X|RL],TL).
/***********************************************/
/**************** Define root-to-leaf paths *****************/
PREDICATES
root2leaf_path(rbt,lr)
CLAUSES
root2leaf_path(t(H,e,e),[H]):-!.
root2leaf_path(t(H,L,R),[H|T]):-
root2leaf_path(L,T);
root2leaf_path(R,T).
/***********************************************/
/******** Convert a List to a Binary Search Tree *********/
PREDICATES
list2bst(lr,rbt)
ins2bst(lr,rbt,rbt)
CLAUSES
list2bst([],e):-!.
list2bst([X],t(X,e,e)):-!.
list2bst([H|T],B):-ins2bst(T,t(H,e,e),B).
ins2bst([],B,B):-!.
ins2bst([H],e,t(H,e,e)):-!.
ins2bst([H],t(X,L,R),t(X,HL,R)):-H<=X,!,ins2bst([H],L,HL).
ins2bst([H],t(X,L,R),t(X,L,HR)):-H>X, !,ins2bst([H],R,HR).
ins2bst([H|T],Ri,B):-
ins2bst([H],Ri,Ria),
ins2bst(T,Ria,B).
/***********************************************/
/**************** Tree Sort *****************/
PREDICATES
tree_sort(lr,lr)
min(lr,r)
max(lr,r)
last(lr,r)
CLAUSES
tree_sort(L,SL):-
list2bst(L,BST),
inorder(BST,SL).
min(L,R):-tree_sort(L,[R|_]).
max(L,R):-tree_sort(L,SL),last(SL,R).
last([H],H):-!.
last([_|T],R):-last(T,R).
/***********************************************/
/******** Height (Depth) of a Rooted Binary Tree *********/
PREDICATES
height(rbt,r)
sublistlens(llr,lr)
lcount(lr,r)
CLAUSES
height(e,0):-!.
height(T,R):-
findall(X,root2leaf_path(T,X),PATHS),
sublistlens(PATHS,L),
max(L,M),
R=M-1.
sublistlens([H],[R]):-!,lcount(H,R).
sublistlens([H|T],[HL|TL]):-
lcount(H,HL),
sublistlens(T,TL).
lcount([_],1):-!.
lcount([_|T],R):-
lcount(T,Ri),
R=Ri+1.
/***********************************************/
/******** Height (Depth) of a Rooted Binary Tree *********/
PREDICATES
height2(rbt,r)
CLAUSES
height2(e,0):-!.
height2(t(_,e,e),0):-!.
height2(t(_,L,R),H):-
height(L,HL),
height(R,HR),
max([HL,HR],M),
H=M+1.
/***********************************************/
/****** Tree Rotation & Heuristic Root-Balancing ******/
PREDICATES
rbt_rotate_right(rbt,rbt)
rbt_rotate_left(rbt,rbt)
root_balance_tree(rbt,rbt)
root_balance_tree(rbt,r,r,rbt)
CLAUSES
rbt_rotate_right(t(Q,t(P,A,B),C), t(P,A,t(Q,B,C))):-!.
rbt_rotate_left(t(P,A,t(Q,B,C)), t(Q,t(P,A,B),C)):-!.
root_balance_tree(e,e):-!.
root_balance_tree(t(X,L,R),T):-
height(R,HR),
height(L,HL),
root_balance_tree(t(X,L,R),HL,HR,T).
root_balance_tree(t(X,L,R),HL,HR,T):-
HL+1<HR,
!, root_balance_tree(L,LL),
root_balance_tree(R,RR),
rbt_rotate_left(t(X,LL,RR),T);
HR+1<HL,
!, root_balance_tree(L,LL),
root_balance_tree(R,RR),
rbt_rotate_right(t(X,LL,RR),T).
root_balance_tree(T,_,_,T).
/***********************************************/
/******** Convert a List to a Root-Balanced Binary
Search Tree using heuristic root-balancing
*********/
PREDICATES
list2rbbst(lr,rbt)
ins2rbbst(lr,rbt,rbt)
CLAUSES
list2rbbst([],e):-!.
list2rbbst([X],t(X,e,e)):-!.
list2rbbst([H|T],B):-
ins2rbbst(T,t(H,e,e),Bi),
root_balance_tree(Bi,B).
ins2rbbst([],B,B):-!.
ins2rbbst([H],e,t(H,e,e)):-!.
ins2rbbst([H],t(X,L,R),t(X,HL,R)):-H<=X,!,ins2rbbst([H],L,HL).
ins2rbbst([H],t(X,L,R),t(X,L,HR)):-H>X, !,ins2rbbst([H],R,HR).
ins2rbbst([H|T],Ri,B):-
ins2rbbst([H],Ri,Ria),
root_balance_tree(Ria,Riab),
ins2rbbst(T,Riab,B).
/***********************************************/
/**************** Heuristic Root-Balancing Tree Sort *****************/
PREDICATES
root_balanced_tree_sort(lr,lr)
CLAUSES
root_balanced_tree_sort(L,SL):-
list2rbbst(L,BST),
inorder(BST,SL).
/***********************************************/
]]>