From strath-cs!cr Tue Nov 17 14:57:04 GMT 1992 Dr. Prosser has pointed out that my solution to the tree deletion is unclear. I actually agree with him. I enclose a new version, with a 'design outline' of the algorithm. I probably made a typing mistake, so please let me know if there are any erros in it. A crucial observation is that the deletion of a node in a tree does not affect any 'parent nodes'; that is, if we locate the node that is to be deleted, we have only to consider its subtrees. If we have a way to combine the two subtrees to form a single, new subtree, then this new subtree will replace the tree rooted at the node we wish to delete. Suppose we wish to delete '3' in the following tree. First, we locate 3. 5 / \ 3 7 / \ 2 4 Then we replace the tree ROOTED AT 3 with a new tree formed by a 'join' operation of its subtrees. There are several possibilities to do this, but as it turns out, there is a consistent way of doing this no matter which binary predicate was used to build the tree. The new tree formed by the join operation looks like this: 4 / 2 Thus we get 5 / \ 4 7 / 2 So, given we have a 'join' operation, deletion of a node is simple. Since it's a binary tree, an element can be either in a left subtree or a right one, but not in both. We exploit this to make the algorithm more efficient. (* delete -- delete an element "x" in a binary tree that has been built with predicate p *) fun delete p x tempty = tempty | delete p x (Tree(l,a,r)) = if x = a then join l r else if p x a then Tree(delete p x l,a,r) else Tree(l,a,delete p x r); Now all we have to do is come up with a join operation. There are four cases that we have to consider. Three of them are trivial. First, joining two empty trees obviously yields the empty tree. Joining an empty tree with a non-empty tree is just as straightforward and simply yields the non-empty tree. Thus our first attempt looks like this: fun join tempty tempty = tempty | join l tempty = l | join tempty r = r | join l r = This_Is_Tricky l r; In other words, all that remains to be done is This_Is_Tricky, which joins two non-empty trees. Since we want to make our algorithm as efficient as possible it is insufficient to simply traverse the two trees and build a new one by tree insertion. This is particularly bad if the trees are traversed inorder, for this yields an ordered list. Insertion of ordered elements into a tree turns the tree into the 'equivalent' of an linked list; that is, all elements are either in the left or right subtrees according to the binary predicate that is used to build the tree. This is where the key idea of the algorithm comes in: in order to join two (non-empty) trees WHICH ARE THE LEFT AND RIGHT SUBTREES OF A COMMON ROOT, we can pull one element out of one tree, make it the root of the joined tree, then delete this node from the tree it came from. Note that one of the trees does not have to be changed at all! A moments reflection on this might convince you that it doesn't matter which tree we leave alone. Here, we elect to leave the left tree alone, and only consider the right one (which is more intuitive since trees are usually built with the 'less_than' predicate). So, we want an element from the right tree, delete it from the right tree, and make this element the root of our new tree with the left tree as left subtree, and the (new) right tree as right subtree (got this??). Consider the following example. 5 / \ 3 7 / / \ 2 6 9 We wish to delete 5. As discussed earlier, we need not bother with the left subtree. We use '6' as new root node (a derivation of this follows), and the tree with '6' deleted as right subtree. Thus we get 6 / \ 3 7 / \ 2 9 as new tree. Note that we can express the new root element and the new (right) subtree as a tuple (new_root,right_subtree). Therefore if we have a function which computes this tuple (given a tree), we have completed the tree deletion (remember, we leave the left subtree alone!). Our next refinement of the algorithm looks thus like this: fun join tempty tempty = tempty | join l tempty = l | join tempty r = r | join l r = let val (new_root,right_subtree) = get_root_and_tree r in Tree(l,new_root,right_subtree) end; But what element do we choose as new root? It will have to satisfy the tree property for both of its subtrees. As far as the left subtree goes, it does not matter! Recall that both trees are the subtrees of a common root. Therefore ANY element of the right tree could be chosen as new root with respect to the left tree. So that was easy. We now concentrate on the the right tree. We are joining two non-empty trees, so the right tree is at least a leaf. If it's just a leaf, then we are already finished because there is only one element which we can choose, with an empty tree remaining. Remember that we shall represent this as a tuple. Thus, exception Impossible; fun get_root_and_tree tempty = raise Impossible (* we know the tree is not empty *) | get_root_and_tree (Tree(tempty,a,tempty)) = (a,tempty) | get_root_and_tree (Tree(l,a,r)) = do_not_know_yet; Let's think about what we do if the tree is a node, ie. has at least one subtree. Which element can we pick? We could pick the root element, but then we would have to (recursively) join its two subtrees (indeed, this is a second efficient solution to the problem). Therefore we do not investigate this possibility, even it would make an interesting (exam???) question. Suppose the tree has a right subtree. Clearly, we cannot choose any element from the right subtree as this would violate the tree property (in the case of our 'less_than' tree, we cannot choose '9' as it violates the '7-6' subtree). This in fact is true even for subtrees of this tree: we may NEVER go to the right! This further simplifies our task; we don't have to worry about right subtrees. So we go left instead. How far 'left' can we go? The answer to this is simple: until we reach a node with no left subtree (since we may never go right, even if the node has a right subtree). In other words, the new root element that we wish to find is the element located in the leftmost node which has no left subtree. Note that we leave the right subtrees alone. Finding the leftmost node is easily accomplished by pattern matching. What's left to do? We notice that if the tree root has no left subtree, then the root element is our 'new root element', and the right subtree is the 'new tree'. Thus we change our previous solution to reflect this. We have finally solved the problem. exception Impossible; fun get_root_and_tree tempty = raise Impossible (* we know the tree is not empty *) | get_root_and_tree (Tree(tempty,a,r)) = (a,r) (* r may be empty or not *) | get_root_and_tree (Tree(l,a,r)) = let val (new_root,new_tree) = get_root_and_tree l in (new_root,Tree(new_tree,a,r)) end; Heureka! Note, however, that this 'join' operation does NOT join two arbitrary trees; rather, all elements in the right tree must satisfy a binary predicate with respect to any element in the left tree (eg. they must be 'greater'). Our algorithm now looks like this: local exception Impossible; fun get_root_and_tree tempty = raise Impossible (* we know the tree is not empty *) | get_root_and_tree (Tree(tempty,a,r)) = (a,r) (* r may be empty or not *) | get_root_and_tree (Tree(l,a,r)) = let val (new_root,new_tree) = get_root_and_tree l in (new_root,Tree(new_tree,a,r)) end in fun join tempty tempty = tempty | join l tempty = l | join tempty r = r | join l r = let val (new_root,right_subtree) = get_root_and_tree r in Tree(l,new_root,right_subtree) end end; fun delete p x tempty = tempty | delete p x (Tree(l,a,r)) = if x = a then join l r else if p x a then Tree(delete p x l,a,r) else Tree(l,a,delete p x r); Does this make sense? I hope it does. Anybody interested in a formal proof of this? It can be done.... Chris