Subject: Re: insert and delete

From: "Richard A. O'Keefe" <[email-masked]>
Date: Wed, 22 Nov 2000 14:36:30 +1300 (NZDT)

Could someone tell me how can I write the following prolog predicates:
	
	insert(Old,N,New) -- succeeds iff Old and New are well-formed BSTs containing
	integers, N is a number, and New is the BST you'd get from inserting N into
	Old. 
	
Start by writing down the BST type.

:- type bst(Element) --> empty | node(Element,bst(ELement),bst(Element)).

You have two cases.  So your predicate will have two similar cases.

insert(empty, N, ?) :- ??how do I insert into an empty tree??
insert(node(V,L,R), N, ?) :- ??how do I insert into a non-empty tree??

Let's take the first case first.  The result of inserting into an empty
tree is going to be node(N,empty,empty).  How do you build that?  Draw a
picture.  So we have our first clause.

insert(empty, N, node(N,empty,empty)).

Now let's take the second case.  The thing about BSTs is that they are
ordered.  It's all going to depend on whether N is less than, equal to,
or greater than V.  So do another case analysis:

insert(node(V,L,R), N, Result) :-
    compare(Order, N, V),
    insert_case(Order, N, Result, V, L, R).

insert_case(<, N, Result, V, L, R) :- ?? how to insert when N @< V ??
insert_case(=, N, Result, V, L, R) :- ?? how to insert when N == V ??
insert_case(>, N, Result, V, L, R) :- ?? how to insert when N @> V ??

Let's take the = case first, because you haven't told us what is to
happen.  Do these BSTs represent SETS (only one occurrence of any value)
or BAGS (any number of occurrences of any value)?  I'll assume sets.
So we just rebuild the tree.

The < and > cases are mirror images.  If N < V, it must be inserted into
the left branch, and the tree reconstructed with a new left branch.

insert_case(<, N, node(V,L1,R), V, L, R) :-
    insert(N, L, L1).

So now we have it.

insert(empty, N, node(N,empty,empty)).
insert(node(V,L,R), N, Result) :-
    compare(Order, N, V),
    insert_case(Order, N, Result, V, L, R).

insert_case(<, N, node(V,L,R), V, L0, R) :-
    insert(N, L0, L).
insert_case(=, _, node(V,L,R), V, L, R).
insert_case(>, N, node(V,L,R), V, L, R0) :-
    insert(N, R0, R).

Note that nothing in this actually depends on N being a number,
only on it (and the elements already in the old tree) being ground.

	delete(Old,N,New)

Do it exactly the same way.  The only tricky thing here is what to do
when you delete V from node(V,L,R).   If L is empty, return R; if R is
empty, return L; otherwise choose one of L, R and promote that one of
its elements which is closest to V.

There really are remarkably few choices to make anywhere in developing
either of these operations.  Certainly none that matter greatly.

It would be a pretty astonishing Prolog book that said nothing about how
to manipulate such trees, and a truly appalling data structures and
algorithms textbook that omitted the topic.