Binary Search Tree: Remove: The Preview
The goal for this exercise is to continue to familiarize yourself with the remove algorithm for binary search trees, using online resources as necessary.
You should located whatever online resources you need in order to become familiar with the binary Search Tree's remove (a.k.a. 'Deletion') logic.
You might start with Wikipedia, although I find the section to be both short & not particularly helpful:
http://en.wikipedia.org/wiki/Binary_search_tree#Deletion
The main idea (from Wikipedia) is this:
· The case of deleting a node with no children (a leaf node) is easy – just remove it from the tree.
· The case of deleting a node with one child is easy – 'splice out' the node we want to remove. This is similar to removing a node from a linked list.
·
The tricky case is
removing a node that has two children. For example, in the following picture
(taken from the Wikipedia page linked to above), imagine that your BST looks
like the MIDDLE tree, and you want to remove "7":
You're basically doing to REPLACE the "7" node with either
"6" (the predecessor – the next smaller) node, or else with
"9" (the successor – the next larger) node. The above picture
attempts to depict this choice (and the resulting trees) by putting the
starting tree in the middle, and the tree that results from "What if we
removed the predecessor?" on the left, and the tree that results from
"What if we removed the successor?" on the right.
Conceptually, this isn't hard, but coding-wise, it can be tricky.
Other online resources (your mileage may vary, so don't spend a lot of time on any one of these, if you get stuck on it):
·
What you need to do for this exercise:
1.
There are no
concrete deliverables for this exercise. You should spend some time making
sure that you’re clear on these concepts, however, since you’ll be using them
to produce concrete results in future exercises.
2. There are no NUnit tests for this exercise