RestTrees

One needs to do deletes. Four situations are possible

the node to be deleted (D) has no children update the parent node to have an empty subtree
the node to be deleted has a left child but no right attach the left subtree of D to the parent
the node to be deleted has a right child but no left attach the right subtree of D to the parent
the node to be deleted has two children

Remember that when the node to be deleted has two children, it can either be replaced by the largest node on the left subtree or the smallest node on the right subtree (to maintain binary tree properties).

Delete 30.

If algorithm chooses to take from right subtree, than want smallest value ... from node to delete (30), go right (35) then left left left until null - at replacement (33)

If algorithm chooses to take from the left subtree, then want largest value ... from node to delete (30) go left (25) then right right right until null - at replace (28)

Delete 40 (replacement from right subtree)

Delete 40 (replacement from left subtree)

One can do it either way in examples/code as long as we are clear and consistent. Specifically, an algorithm does it one way or another (not back and forth).

Code which replaces a node with two children with largest node on the left subtree:

So, it selects, as the replacement R, the rightmost node in the left subtree. This is the largest node whose data value is less than that of the node to be deleted.

Unlink this node R from the tree,
connect its left subtree to its parent,
and then connect R at the deleted node.

The following is from another book (Page 588 Data Strucutres with C++ (Ford and Topp)) that has defined a FindNode method (to find the node AND its parent). This Delete method does not return anything.

public void delete(String x){ delete (root, x); } private void delete(Node PNode, String x) Node DNode, RNode; // DNode node D that is deleted // PNode parent of D, initially PNode is root // RNode node R will replace D // Search for a node containing data value item, obtain is node address // and that of its parent // Specifically, FindNode will return DNode // and change the value of PNode to parent of DNode if ( (DNode = FindNode(x, PNode)) == null) return; // If D only has one child, that side is the replacement node (case 2 and 3) // Notice the default here, if there are NO children, then RNode stays null (case 1) if (DNode.right == null) RNode = DNode.left; else if (DNode.left == null) RNode = DNode.right; // both children are non-null else { // find and unlink replacement node for D. // starting on the left branch of node D // find node whose data value is the laargest of all // nodes whose values are less than the value in D // Unlink the node from the tree // PofRNode is the parent of the replacement node PofRNode = DNode; // first possible replacement is left child of D RNode = DNode.left; // descend down the right subtree of the left child of D, // keeping a record of current node and its parent // when we stop, we have found the replacement while (RNode.right != null) { PofRNode = RNode; RNode = RNode.right;} if (PofRNode == DNode) // left child of deleted node is the replacement // assign a right subtree of D to R RNode.right = DNode.right; else { // we move at least one node down a right branch // delete replacement node from tree by assigning // its left branch to its parent PofRNode.right = RNode.left; //put replacement node in place of DNode RNode.left = DNode.left; RNode.right = DNode.right; } } // complete the link to the parent node // deleting the root node, assign a new root if (PNode == null) root = RNode; // attach R to the current branch of P else if (DNode.word.compareTo(PNode.word) < 0) PNode.left = RNode; else PNode.right = RNode; }

Implementation Discussion

Issues: Note if you are reading these notes and not listening to a lecture:
- this section is "thinking out loud" to consider (and be aware of) possibilities.

What should the ADT specification look like?

What methods and what variables?

Methods are Search, Find (to provide parent as well), Insert, Delete (maybe Join, Split). Which should be public? which private?

What should the IVs be?

Some depends on implementation and where to hold the information. For example, one does a Find so you can use the info in an Insert or Delete. Should the results of a Find be passed back to the calling method or should they be put in IVs?

This is a question you should always consider. If other methods are going to make use of the variables too, it is better to put them into IVs.

IVs and CVs are always providing information about the state of the object.

If other methods need to know this state, let them have it easily (i.e., provide it in IVs). If in a method, the state is changing, maybe it is useful to have this information. (Example, I am searching the binary tree and am at node curNode...whatever)

However, always consider implementation. What if you wanted to do a Find in parallel? That is, do it recursively (left and right subtrees with separate threads). They would be accessing the same variable and the "state" is never settled until the end of the recursion. Maybe trouble.
Consider using recursion (and hence, perhaps concurrency). Could we use concurrency for every method?
Good question... In fact, as it is already, should any of our methods be synchronized to prevent concurrency?

In other languages one did not need to think about this, but suppose someone spawned a bunch of threads to do Inserts (or Deletes) in parallel. Trouble.

Solution? Of course, synchronize. But remember, "when one thread enters a synchronized method, Java guarantees that it can finish it before another thread can execute any synchronized method in the same object." Here, our bst can block threads and notify them when it becomes available so it is behaving as a monitor. (In Java, any object with one or more synchronized methods is a monitor.) Which methods need to be monitored?

Clearly, Insert and Delete.

Which methods could be done using parallelism via recursion? Search and Find.

Note that this makes one see the usefulness of small, single purpose methods. We might want to do the searches with multiple threads, but if they are inside of the Insert or Delete, then the concurrency is useless. Methods that are synchronized should always be as small as possible. It is only the part that deals with changing the critical variable that should be synchronized.

So, for example, in the binary trees method insert, the high level insert could find where to put the node (and what this nodes parent is) and then call a lower level synchronized part that makes the change.

Hmmm, suppose a bunch of Finds are done (and waiting) and info has changed since Find was done. sigh. One often sees objects that might be changed while another is being worked on be cloned first. However, that does not work for data integrity, only for the idea of working on what was there when the work was started. How about checking a flag when one enters Find or Search that indicates a change is in the middle of being made (set upon entry into and exit out of Delete/Insert, and wait for it (sleep (is wait only for sychronizedthreads? notifyAll() (which must be in synchronized) notifies all threads to wake up and check some condition... Remember we do not want to synchronize here since we are trying to call recursion.)