There are many applications that require maintaining of objects based on a key value. For example, we may have an application program that needs to keep track of employees. For the most part, employees are uniquely identified by their Social Security number. Imagine that our application allows an end-user to add or remove employees or update their information. May be, we would like the program to filter employee records and give reports on how many of different levels of employees we have. What is the best way for us to keep track of these employees?
At this point, it should be easy for you to think about storing them in an array or a linked list, sequentially search for them, remove some or add new ones. But, a simple array or linked list may not give us the performance that we like. The performance of most of our operations is O(n) when we utilize a simple sequential data structure.
What the application wants to do with employee information has something to do with our decisions on how store and manage the information. Yet, there is a significant level of commonality between applications that need to keep keyed objects.
We want a key for objects because we want them to be unique and we like to be able to retrieve them based on their key. We also have learned that it is best to leave things general, if possible, when designing classes. Doing so, provides us with the ability to reuse already developed classes in many applications. Keyed Collections seem to fit this generalization well. What is the difference between an employee and a part? Can you not think of an application that would maintain parts and provide the same functionality as we said we would for employees? Even the more far fetched example like a dictionary with words and their meanings can be thought of as a keyed collection.
As you will see keyed collections are not designed to anticipate all functionality required by all applications; they are designed to address the most common requirements for storing keyed data. We can always extend such collections to satisfy the needs specific to a particular application.
keyedCollection is defined as an interface below, as you can see it allows us to find/add/remove/update Keyed objects. It also has some helper methods, one to check if the Collection is empty and the other to output the structure and data in the collection (the dump method is intended to help with debugging, not really intended for an end-user).
What is an interface? An interface is similar to an abstract class in that there is no code associated with its methods. However, in Java a class can be designed to implement any number of interfaces, but can only extend one class.
Here is the definition for keyedCollection. Pay close attention to the return values, parameter types, and exceptions of the methods.
public interface keyedCollection {
public void add(Keyed x) throws duplicateException;
public void remove(String key) throws notFoundException;
public void update(Keyed x) throws notFoundException;
public Keyed find (String key) throws notFoundException;
public boolean empty();
public void dump();
}
Keyed is also an interface. So, any class can implement it. For example, an Employee class can implement it, a DictionaryElement class can implement it; basically, anything that we would consider storing in a keyedCollection would implement Keyed. So, what does it mean when we say something "implements" something else? First, it has to be defined that way, for example, we would say class Employee implements Keyed ... in the header of the class. But more importantly, this definition obligates such a class to have the methods that the interface says it must have. In the case of Keyed, we are saying that any class that implements it must have a key() method.
public interface Keyed {
public String key();
}
Why is it useful for all objects stored in a collection to have a key method? Why use a String object for the return value? Well, if a collection needs to verify that a particular employee or part or any Keyed object is in fact stored in it, it can use the key method of its objects to determine that. Without such an interface we can not implement a clean and general class that implements keyedCollection. All classes that implement Keyed must be designed to have their key method return a unique string that identify them. For example, an employee object would return the SS# of the employee. Even if the actual key information is an integer or float, we have methods in the String class to convert it to string.
We are going use the Binary Search Tree as a class that implements keyedCollection. BST keeps unique elements and as long as we have a way of comparing them it is easy to place new nodes in it or find existing ones.
Let us first define Trees and Graphs, keeping in mind that there is much more to them than just a Binary Search Tree. We will discuss these further in subsequent courses.
A Graph is a collection of nodes/vertices connected by lines or edges.
A Tree is a specialization of a graph where the edges are directed with the concept of a single starting point, a root, and only one path to any given node in the tree. This means that we can't have cycles (a node pointing back to an ancestor) and no node can have more than one parent. There is an inherent parent-child relationship between nodes embedded in this definition which we will take advantage of for defining BSTs. There is also a clean and important concept of a subtree. Take out any edge connecting two nodes of the tree, what you end up with is the original tree with a portion of it pruned off, and what we refer to as a subtree which is also a tree; the proof for this is fun, but I'll let it go for now.
The heuristic for Binary Search Tree is well defined and simple; note that it is a recursive.
A Tree is a Binary Search Tree iff ...
Lets demonstrate with a few example:
45 33 4 40
/ \ / \ \ / \
12 60 20 40 5 7 70
/ \ \ \ \ \ /
3 20 65 34 6 9
BST NOT BST BST NOT BST
As mentioned before we will use BST for implementing keyedCollection. There are several good reasons for this. BST's structure lends itself well to search processes that look for a particular element, you travel the height of the tree to find something. Adding and removing are not costly either, each only requiring traversal of a single path to the bottom at worst case. As the 3rd example above shows, it is possible to turn a tree into a linked list; however, it is only the worst case scenario. We have found that BST performs close to log(n) in average cases for add, remove, and find.
To start implementing a BST, we need to define our node. A node here will hold a Keyed element and two references, one to the left subtree and the other to the right. Here is the code:
public class treeNode {
public Keyed element;
public treeNode left;
public treeNode right;
public treeNode (Keyed k, treeNode l, treeNode r) {
left=l;
right=r;
element=k;
}
}
The header for Tree class (our BST) will look like this: public class Tree implements keyedCollection as it needs to be declared as a class that "implements" keyedCollection.
The only state variable in this class is root which is a treeNode and initially set to null. The constructor for Tree does nothing. In the following sections, we will discuss the details of add, remove, and dump methods.
Lets consider the add method. First of all Tree has to have an add method since keyedCollection identified it as a method that must be implemented. Here is the code:
public void add(Keyed x) throws duplicateException {
try {
find(x.key());//If find doesn't throw an exception, add needs to
throw new duplicateException(x);
}
catch (notFoundException e) {
// x not found in tree, go ahead and insert
root=insert(root,x);//use recursive insert to add x to the tree
}
}
There is plenty of stuff here to get confused about. First of all why do we throw the duplicateException, but catch the notFoundException? It has to do with the clever use of find. Note that, the find method is called with the key of the object being added as its parameter. Note that find may throw the notFoundException; however, in the context of add this a good thing! If we call find and it throws an exception (the key is NOT found), we know that our object does not already exist in the tree, so we can proceed with putting it in. Notice that we don't store the return value from find anywhere, as we only care about the exception that it may throw. If find does not cause the notFoundException, we execute the throw new duplicateException(x);. As I will discuss later, even though, using find seems like a good idea here, it is certainly not the most efficient way of handling duplicate exceptions for add.
The insert method is written recursively, not because we had to do it that way, but only to provide yet another example of recursion. The statement root=insert(root,x); makes it possible to modify root. We had seen this technique when discussing mergeSort earlier in the semester.
Let us now look at the code for insert:
private treeNode insert (treeNode root, Keyed x) {
if (root == null) return new treeNode(x,null,null);
if (root.element.key().compareTo(x.key()) < 0)
root.right = insert (root.right,x);
if (root.element.key().compareTo(x.key()) > 0)
root.left = insert (root.left,x);
return root;
}
in reading a statement like if(root.element.key().compareTo(x.key())<0), keep in mind that root references a treeNode object. in that object, we have an element which is a Keyed object. Keyed objects have a key method that returns a String object. String objects have a compareTo method that compare their content against another String object's content, in this case x.key().
It is easy to see that this algorithm traverses down a path in the tree and does not stop until a null reference to the tree or a subtree is encountered. Yet, the most fundamental aspect of insert which is the process of attaching the newly created node to the rest of the tree is the least obvious element of this algorithm. The code for attaching the new node is hidden away in the recursion here. Lets use an example to show how it works:
Suppose a tree is in the following state:
root
10
/ \
5 20
/ \
15 30
Let us insert a 17 into this tree. Since 17 is not already in the tree, we expect insert to be called and we execute the following statement (I hope my crude syntax here makes sense):
root = insert (root,x); 1st call
10 17
/ \
5 20
/ \
15 30
Since root is not null, we decide which way to go, and recursively call insert:
root.right = insert (root.right,x); 2nd call
20 17
/ \
15 30
root is not null, so we recursively call insert again:
root.left = insert (root.left,x); 3rd call
15 17
This will be the last call to insert, since root.right is null, the root parameter will be null upon entry:
root.right = insert (root.right,x); 4th call
null 17
At this point, a new node is created with 17 in it and returned. But where does it return to and what do we do with it? We are going to return the new node to where the 4th call to insert was made from, which as you can see places the return value in root.right. consequently, making that subtree look like the following:
root
15
\
17
Note that the last instruction executed in the method is return root; This statement is designed to reattach the rest of the tree as we return from each recursive call, finally, making the tree look like the following:
root
10
/ \
5 20
/ \
15 30
\
17
This reattachment technique is great because it has very little over head and we don't have to think about our subtrees changing in subsequent recursive calls. There is no need for checking to see if the right or left branches have changed. We just replace branches with themselves if they have not changed and if they have changed, they take on the new value.
The algorithm for removal of elements from a tree is a bit more complicated than the one for adding elements. There are three cases that must be handled here, two of which are simple. When deleting an element, you must traverse the tree until you locate the node that it is in, this, of course, assumes that the element exists in the tree. The node being deleted may be a leaf (no children) or it may have only one offspring, a left child, or a right child. These cases are simple to handle as you will see later. The third case is a bit more complicated and it deals with a node being removed that has both a left and right child. Keep in mind that when I say a left or right child, I am really talking about subtrees, so we don't know how many levels each have.
The remove method is designed similarly to the add method in that it calls a recursive method, del, to actually remove an element based on its key. remove also makes use of find to determine if an element really exists in the tree. But, why does not need a try/catch? It is simple, remove throws the same exception as find does. In Java, when a method is declared to throw an exception that may be thrown by one of the methods that it calls, the called method does not have to appear in a try/catch. If find throws the exception, remove automatically will also throw the exception.
Lets consider the code for del piece by piece. Again, first we need to located the appropriate node to be deleted, then determine which case we are dealing with and of course take appropriate action to remove the node.
This segment is very similar to what we did in insert and is designed to traverse the tree recursively until the node that we want to delete is found. Notice that it uses the same technique for reconnecting the tree, for example, root.left=del(root.left,key); will reconnect a node to its left subtree and not bother worrying about if it was changed or not.
if (root.element.key().compareTo(key) < 0) { //go right
root.right = del (root.right,key);
return root;
}
if (root.element.key().compareTo(key) > 0) { //go left
root.left = del (root.left,key);
return root;
}
Now, the rest of the code deals determining which case we have and handling it. The first two if statements deal with a node being deleted that has a left subtree, or a right subtree, or none at all.
if (root.left == null)
return root.right; //since there is no left side replace root with right
if (root.right == null)
return root.left; //since there is no right side replace root with left
Here are a couple of examples to show what happens here. Consider the following tree:
root
10
/ \
5 20
/ \
15 30
\
17
Suppose we like to delete the 5 from this tree, we call del from remove with the following call:
root=del(root,key);
10 5
/ \
5 20
/ \
15 30
\
17
Since 5 is less than 10, we go left using:
root.left=del(root.left,key);
5 5
Upon entering del we find out that we don't want to go left or right, so we have the correct node. Then we check root.left against null, since it is null, we return root.right. In this case, notice that we are returning null as the root.right is also null.
At the previous level of recursion, the root gets reconnected with its left side, which is now null. So, the tree will look like the following and gets returned to remove.
root
10
\
20
/ \
15 30
\
17
Suppose we like to delete the 15 from the original tree, we call del from remove with the following call:
root=del(root,key);
10 15
/ \
5 20
/ \
15 30
\
17
Since 15 is greater than 10, we go right using:
root.right=del(root.right,key);
20 15
/ \
15 30
\
17
Since 15 is less than 20, we go left using:
root.left=del(root.left,key);
15 15
\
17
Again, we find out that we have found the correct node that its left side is null. root.right is returned. When the root at the previous level gets reconnected with its left side, we end up with:
root
20
/ \
17 30
This subtree is returned to the previous level of recursion and root, at that level, is reconnected with its right side and the tree is returned to the remove method. The tree will look like the following:
root
10
/ \
5 20
/ \
17 30
In summary, for the simple cases, once we locate the node being deleted, we return either its left or right subtree. Now, on to the interesting case, when the node being deleted has both a left and right subtree.
When a node has both a left and right subtree, we do not delete it; yet, we need to get rid of its element. So, the technique is to find either its successor node or predecessor node, exchange contents and remove that node.
What node is considered a successor? The successor to any node in a tree, is the node that contains the next largest value. In our original tree, the successor to 10 is 15. How does one locate the successor node? Start from the root of the right subtree of the node that we wish to find the successor of, and follow the left branches of each subsequent node until the left most node in that subtree is found. That node contains the successor.
Once the successor is located, the elements ar exchanged and we continue the recursive delete process in the direction of the right subtree. Lets show this by deleting 10 from our original tree. del will be called with following:
root=del(root,key);
10 10
/ \
5 20
/ \
15 30
\
17
for(temp=root.right;temp.left!=null;temp=temp.left); is designed to locate the successor node. Keyed x = temp.element;temp.element=root.element;root.element=x; exchanges element in the root for the element in the successor. So, the tree will look like this:
root
15
/ \
5 20
/ \
10 30
\
17
keep in mind, even though this is not a BST at this instant, we are not done yet, the search delete process continues with:
root.right = del (root.right,key);
20 10
/ \
10 30
\
17
Since element in root is greater than 10, we go left with:
root.left = del (root.left,key);
10 10
\
17
Found the right node, this time, however, there is only a right subtree, so we simply return it in place of root. Once all recursive steps are completed, the tree will look like this:
root
15
/ \
5 20
/ \
17 30
the dump uses a recursive method print to display all keys in the tree in the form of a tree. Here, I'll simply discuss the concept of inOrder traversal which is what print utilizes.
inOrder traversal is a special way of visiting all nodes in a tree; usually, it means that we visit the left subtree, consider root, then visit the right subtree. Keep in mind that in paint, we visit the right subtree, display the key in the root, then visit the left subtree.
Here is the basic algorithm:
inOrder traversal
if root is not null
apply inOrder traversal to left subtree
display key in root
apply inOrder traversal to right subtree
To make inOrder traversal clear, let us follow this example:
root
15
/ \
5 20
/ \
17 30
First we traverse left. Since this subtree only has the node with 5, no left or right child, we display 5 and return. We then display 15 when we return to the previous level of recursion. Now we traverse right, the subtree there looks like:
root
20
/ \
17 30
Again, first we traverse left, and display 17. Then we display the 20, then we traverse right and display 30. Note that all nodes were visited with this algorithm and the list of elements is displayed in ascending order.