% ==========================================================================
% $Id: bst.pl,v 1.1 2014/01/28 06:18:50 jlang Exp $
% CSI2120 example Code for lecture 7
% ==========================================================================
% (C)opyright:
%
%   Jochen Lang
%   SITE, University of Ottawa
%   800 King Edward Ave.
%   Ottawa, On., K1N 6N5
%   Canada. 
%   http://www.eecs.uottawa.ca/~jlang
% 
% Creator: jlang (Jochen Lang)
% Email:   jlang@eecs.uottawa.ca
% ==========================================================================
% $Log: bst.pl,v $
% Revision 1.1  2014/01/28 06:18:50  jlang
% Added tree and graph examples.
%
% ==========================================================================

% Sorting criteria (numbers only)
precedes(Key1, Key2) :-
            Key1 < Key2 .

% find
binarySearch(Key, t(Key, _, _)).
binarySearch(Key, t(Root, Left, _)) :-
    precedes(Key, Root),
    binarySearch(Key, Left).
binarySearch(Key, t(Root, _, Right)) :-
    precedes(Root, Key),
    binarySearch(Key, Right).


% insert
insert(Key, nil, t(Key, nil, nil)).
insert(Key, t(Root, Left, Right), t(Root, LeftPlus, Right)) :-
    precedes(Key, Root),
    insert(Key, Left, LeftPlus).
insert(Key, t(Root, Left, Right), t(Root, Left, RightPlus)) :-
    precedes(Root, Key),
    insert(Key, Right, RightPlus).


% deleteBST
%%%%%%%%%%%%%
% boundary case right-most node is maximum
removeMax(t(Max, Left, nil), Left, Max).
% recursion on the right of the root node (for tree nodes sorted with
% less than).
removeMax(t(Root, Left, Right),
	t(Root, Left, RightSmaller), Max) :-
    removeMax(Right, RightSmaller, Max).


% Boundary case replace node with the right subtree
deleteBST(Key, t(Key, nil, Right), Right).
% Boundary case replace node with the left subtree
deleteBST(Key, t(Key, Left, nil), Left).
% DeleteBST current and replace with maximum
deleteBST(Key, t(Key, Left, Right),
	t(NewRoot, NewLeft, Right)) :-
     removeMax(Left, NewLeft, NewRoot).


% Search on the left subtree for key to delete
deleteBST(Key, t(Root, Left, Right),
		t(Root, LeftSmaller, Right)) :-
	precedes(Key, Root),
    	deleteBST(Key, Left, LeftSmaller).
% Search on the right subtree for key to delete
deleteBST(Key, t(Root, Left, Right),
		t(Root, Left, RightSmaller)) :-
	precedes(Root, Key),
	deleteBST(Key, Right, RightSmaller).


% ?- treeA(X), deleteBST(83,X,V).