The programming language Prolog is different from procedural programming languages like C or even functional programming languages like Haskell in that instead of functions, Prolog is based entirely on predicates which return only "true" or "false" as answers but can bind any variables it wishes, thus allowing the interpreter to do seemingly magical things; for example, a program marking whether a string belongs to a context-free language can, by not binding the variable and letting the Prolog interpreter do so instead, be used to generate a string in said language, if the program is coded carefully. Another example of this is that it is possible to implement binary search trees in such a way that insertion and deletion are performed using the same code; given the predicate insert(T1,X,T2), if T1 is bound but T2 is left unbound, then a tree identical to T1 with X inserted will be bound to T2, while if T2 is bound but T1 is left unbound, then a tree identical to T2 but with X deleted will be bound to T1.
The following is naive code for insertion in a binary search tree: bst(Left,Value,Right) is used to represent a non-empty tree(this representation has the advantage of having its elements in sorted order when displayed by the Prolog interpreter), while leaf is used to represent an empty tree.
insert(bst(L,A,R),X,bst(LX,A,R)) :- A > X, insert(L,X,LX).
insert(bst(L,A,R),X,bst(L,A,RX)) :- A < X, insert(R,X,RX).
insert(leaf,X,bst(leaf,X,leaf)).
This code, when used in such a way to insert an element, works exactly as expected; it also works as expected if you attempt to delete a leaf from the tree; however, if you attempt to delete a node which is not a leaf, the code will fail. Instead, we use code based on the code from the
random binary search tree page, and take advantage of the branching offered by Prolog, and allow a value X to be inserted at any point by either descending further down the tree or splitting the tree into the parts of the tree larger and smaller than X and making them the new left and right subtrees(the latter method is equivalent to descending a tree, then using a series of rotations as in the
AVL tree to bring it to the top of the scale); the code is as follows:
split(leaf,_,leaf,leaf).
split(bst(L,A,R),X,L1,bst(L2,A,R)) :- A > X, split(L,X,L1,L2).
split(bst(L,A,R),X,bst(L,A,R1),R2) :- A < X, split(R,X,R1,R2).
insert(bst(L,A,R),X,bst(LX,A,R)) :- A > X, insert(L,X,LX).
insert(bst(L,A,R),X,bst(L,A,RX)) :- A < X, insert(R,X,RX).
insert(T,X,bst(L,X,R)) :- split(T,X,L,R).
The following code works as you expect it to for both insert and delete; furthermore, if one presses the semicolon key after getting the results for an insertion or deletion, one gets the many ways in which this code allows it to be inserted.