CS计算机代考程序代写 prolog % CPSC 312 – Binary Search Trees in Prolog

% 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/

% 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(V,e,bnode(2,b, bnode(1,a,empty,empty), bnode(5,e,empty,empty))). % Why does it give an error?

% 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).