Binary Search Trees

A binary search tree is a special form of binary tree that contains
comparable objects stored so that every element in the left subtree is
less than the root, and every element in the right subtree is greater
than the root.

A comparable object is one that implements the Comparable interface,
which means that it has a compareTo method that will compare it to
another object of the same type, and return -1, 0, or 1 if the object
is less than, equal to, or greater than the object it is being
compared to, respectively.  The definition of "greater" or "less" is
dependant on the object type.

Supports operations 
- contains
- getEntry
- add
- remove
- getIterator

Duplicate entries can be allowed, but they complicate the issue.  If
you allow duplicate entries, then you must always place them to the
left or the right, consistently.  It also raises the problem of which
to return on a getEntry, and which to remove on a remove.  These
problems are not insurmountable, but they make the logic of the tree
more complicated.  Many applications do not need to store duplicates.

If you extended the tree interface, you must now disallow the explicit
setting of the right and left subtrees, and the node data, because the
bst maintains the data in an ordered fashion.

Lets examine the methods

contains has a nice recursive solution

public boolean contains(bst tree, Object o){
			 // base case 1
			 if (bst.isEmpty()){						 
					return false;
			 }
			 // base case 2
			 else if (o.compareTo(tree.root) == 0){
					return true;
			 }
			 // recursive case 1
			 else if (o.compareTo(tree.root) < 0){
				  return contains(tree.leftChild(), o);		
			 }
			 // recursive case 2
       else {
					return contains(tree.rightChild(), o);
			 }			 
}

The solution to getEntry is exactly the same, but in the first case,
you would return null rather than false, and in the second case you
would return tree.root rather than true;

so, you could equally well just write getEntry, and have contains 
return getEntry(o) != null.

when we add a new entry, we have to maintain the ordering of the
binary tree, which says that all elements in the left subtree are less
than the root, which is less than all the elements in the right
subtree.  There is also a very nice recursive solution for this (for
an iteratove solution, see chapter 26 in the book.  You will notice
that it is a much uglier piece of code).

public Comparable add(bst tree, Object o){

			 // base case
			 if (bst.isEmpty()){
					bst = new Node(o);
					return null;
			 }
			 // recursive case 1
			 else if (o.compareTo(tree.root) < 0){
						return add(tree.left, o);
			 }
			 // recursive case 2
			 else if (o.compareTo(tree.root) > 0){
						return add(tree.right, o);
			 }
			 // base case 2
			 else {
						Object retVal = tree.root; 
						tree.root= o;
						return retVal;
			 }

}

Remove is a bit trickier.  When we remove a node, we still need to
preserve the ordering of the tree, even though we may be yanking out a
node that has children.  There are really three cases to consider
(four, with the root node).

The first case is that we are removing a node with no children.  This
is the simplest case.  All you have to do is to set the node to be the
empty node, and voila, case closed.

The second case is that the node has one child, either right or left.
In this case, you will have to simply assign the child to be the same
child as the node you are removing, or sort of pick up the tree by the
child, and re-root it in the removed nodes place.  So, if you are
removing the right child of a node, you would put the removed node's
child into the right child spot, regardless of if it was a right or
left child of the removed node, and the same for the left.

The tricky case is where we need to remove a node that has two
children.  Since we can't assign both of the removed nodes children to
its parent, we need to think of a better solution.  

So, what we'll do, is replace the node that we are removing with
another node in the tree that is easy to remove, but that will
preserve the binary ordering.  Which node is that?  Well, it should be
the node that comes either immediately before or after the node to
remove in an inorder traversal.  Which nodes are these?  Either the
rightmost of the left subtree, or the leftmost of the right subtree.

If we are removing the root of the tree, we proceed as normal, but the
root pointer will need to be switched.  This is only true if the root
has one child, because otherwise we will be switching the value, and
deleting the switchee.

for a complete implementation of these methods, see chapter 26 in the
text.


Balancing trees

When a tree is balanced, finding a node takes O(log n) time.  However,
at the worst case of an unbalanced tree, it can take O(n) time.  When
a tree is static, you can get good performance, but dynamic additions
and removals can mess with a well balanced tree.

Tips : never add nodes in a sorted order.  The ideal way is to add
from the middle, but a random ordering is actually a pretty good way
to get a tree set up.