% CPSC 312 – Binary Search Trees in Prolog
% Copyright D Poole 2021, Released under CC BY-NC-SA 4.0 https://creativecommons.org/licenses/by-nc-sa/4.0/
:- use_module(library(clpfd)). % defines #< and #> for integers..
% A binary search tree is either
% empty or
% bnode(Key, Val, T0, T1) where Key has value Val and T0 is the tree of keys less than Key and T1 is the tree of keys greater than Key
% val(K, V, T) is true if key K has value V in tree T (K must be ground)
val(Key, Val, bnode(Key, Val, _,_)).
val(Key, Val, bnode(K1, _, T0, _)) :-
Key #< K1,
val(Key, Val, T0).
val(Key, Val, bnode(K1, _, _, T1)) :-
Key #> K1,
val(Key, Val, T1).
% val(1,V, bnode(2,b, bnode(1,a,empty,empty), bnode(5,e,empty,empty))).
% val(4,V, bnode(2,b, bnode(1,a,empty,empty), bnode(5,e,empty,empty))).
% val(K,V,bnode(2,22, bnode(1,57,empty,empty), bnode(5,105,empty,empty)))
% val(K,V,bnode(2,22, bnode(1,57,empty,empty), bnode(5,105,empty,empty))), V #< 99.
% V #< 99, val(K,V,bnode(2,22, bnode(1,57,empty,empty), bnode(5,105,empty,empty))).
% insert(K, V, T0, T1) T1 is the result of inserting K=V into tree T0
insert(K,V,empty, bnode(K,V,empty,empty)).
insert(K,V,bnode(K,_,T0,T1), bnode(K,V,T0,T1)).
insert(K,V,bnode(K1,V1,T0,T1),bnode(K1, V1, T2, T1)) :-
K #< K1,
insert(K,V,T0,T2).
insert(K,V,bnode(K1,V1,T0,T1),bnode(K1, V1, T0, T2)) :-
K #> K1,
insert(K,V,T1,T2).
% insert(4,d,bnode(2,b, bnode(1,a,empty,empty), bnode(5,e,empty,empty)), R).
% insert(4,d,bnode(2,b, bnode(1,a,empty,empty), bnode(5,e,empty,empty)), R), insert(7, G, R, R1).
% What do you expect the following to give?
% val(4,d,T), val(1,a,T).
% val(1,a,T), val(4,d,T).
% val(4,d,T), val(1,a,T), val(2,b,T), val(1,V,T).