A binary search tree (BST) relies on the property that keys that are less than the parent are found in the left subtree, and keys that are greater than the parent are found in the right subtree. We will call this the BST property. As we implement the Map interface as described above, the BST property will guide our implementation. Figure 6.14.1 illustrates this property of a binary search tree, showing the keys without any associated values. Notice that the property holds for each parent and child. All of the keys in the left subtree are less than the key in the root. All of the keys in the right subtree are greater than the root.
Figure6.14.1.A Simple Binary Search Tree
Subsection6.14.1Constructing a Binary Search Tree
Now that you know what a binary search tree is, we will look at how a binary search tree is constructed. The search tree in Figure 6.14.1 represents the nodes that exist after we have inserted the following keys in the order shown: \(70, 31, 93, 94, 14, 23, 73\text{.}\) Since 70 was the first key inserted into the tree, it is the root. Next, 31 is less than 70, so it becomes the left child of 70. Next, 93 is greater than 70, so it becomes the right child of 70. Now we have two levels of the tree filled, so the next key is going to be the left or right child of either 31 or 93. Since 94 is greater than 70 and 93, it becomes the right child of 93. Similarly 14 is less than 70 and 31, so it becomes the left child of 31. 23 is also less than 31, so it must be in the left subtree of 31. However, it is greater than 14, so it becomes the right child of 14.
To implement the binary search tree, we will use the nodes and references approach similar to the one we used to implement the linked list and the expression tree. However, because we must be able create and work with a binary search tree that is empty, our implementation will use two classes. The first class we will call BinarySearchTree, and the second class we will call TreeNode. The BinarySearchTree class has a reference to the TreeNode that is the root of the binary search tree. In most cases the external methods defined in the outer class simply check to see if the tree is empty. If there are nodes in the tree, the request is just passed on to a private method defined in the BinarySearchTree class that takes the root as a parameter. In the case where the tree is empty or we want to delete the key at the root of the tree, we must take special action. The code for the beginning of the BinarySearchTree class is shown in Listing 6.14.2.
import java.util.Iterator;
class BinarySearchTree<K extends Comparable<K>,
V extends Comparable<V>> {
TreeNode root;
int size;
public BinarySearchTree() {
this.root = null;
size = 0;
}
public int size() {
return size;
}
public TreeNode getRoot() {
return root;
}
Listing6.14.2.
Note6.14.3.Java Note.
There are several new Java constructs to unpack here. First, in lines 3 and 4, we define this class as requiring two generic data types, K for the key and V for the value. We may need to do comparisons on both keys and values, so we want to make sure each data type extends Comparable.
We would also like to be able to use an extended for loop to iterate through a BinarySearchTree, so we need to import the Iterator class in line 1. We will add the code for iteration in Subsection 6.14.5.
The root and size properties are not declared to be either public or private. Instead, they have default access; other classes and subclasses in the same package (in this case, in the same directory as this file) can access the properties. For convenience, we will be using this default access for everything that does not need to be public.
The TreeNode class provides many helper methods that make the work done in the BinarySearchTree class methods much easier. The constructor for a TreeNode, along with these helper methods, is shown in Listing 6.14.4. We will put this class definition inside the BinarySearchTree class. This will automatically give a TreeNode access to all the BinarySearchTree properties, including the generic types K and V. As you can see in the listing, many of these helper methods help to classify a node according to its own position as a child (left or right) and the kind of children the node has. The TreeNode class will also explicitly keep track of the parent as an attribute of each node. You will see why this is important when we discuss the implementation for the remove method in Subsection 6.14.6.
We have overloaded the constructor. In lines 16–22, the constructor is given all the information a TreeNode needs. Sometimes, though, we want to construct a TreeNode without only some of the information. The constructors in lines 8–14 call the 5-argument constructor to provide the “missing” arguments. (Using this as a method name calls the constructor.)
class TreeNode {
K key;
V value;
TreeNode leftChild;
TreeNode rightChild;
TreeNode parent;
TreeNode(K key, V value) {
this(key, value, null, null, null);
}
TreeNode(K key, V value, TreeNode parent) {
this(key, value, null, null, parent);
}
TreeNode(K key, V value, TreeNode left, TreeNode right, TreeNode parent) {
this.key = key;
this.value = value;
this.leftChild = left;
this.rightChild = right;
this.parent = parent;
}
/* Is this node a left child of a parent? */
boolean isLeftChild() {
return parent != null && parent.leftChild == this;
}
/* Is this node a right child of a parent? */
boolean isRightChild() {
return parent != null && parent.rightChild == this;
}
/* Is this the root node? (The root node has no parent) */
boolean isRoot() {
return parent == null;
}
/* Is this a leaf node? (Leaf nodes have no children) */
boolean isLeaf() {
return (leftChild == null && rightChild == null);
}
/* Does this node have any children? */
boolean hasAnyChild() {
return leftChild != null || rightChild != null;
}
/* Does this node have both left and right children? */
boolean hasChildren() {
return leftChild != null && rightChild != null;
}
void replaceValue(K key, V value, TreeNode left, TreeNode right) {
this.key = key;
this.value = value;
this.leftChild = left;
this.rightChild = right;
if (this.leftChild != null) {
this.leftChild.parent = this;
}
if (this.rightChild != null) {
this.rightChild.parent = this;
}
}
public K getKey() {
return this.key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return this.value;
}
public void setValue(V value) {
this.value = value;
}
public String toString() {
String keyStr = (key == null) ? "null" : key.toString();
String valStr = (value == null) ? "null" : value.toString();
return "key: " + key + " value: " + value + "\n " +
" left: " + leftChild + " right: " + rightChild +
"parent: " + parent;
}
}
Listing6.14.4.
Note6.14.5.Java Note.
Lines 84 and 85 introduce Java’s ternary operator. Writing an expression of the form:
Subsection6.14.2Inserting Keys and Values into a Binary Search Tree
Now that we have the BinarySearchTree shell and the TreeNode, it is time to write the put method that will allow us to build our binary search tree. The put method is a method of the BinarySearchTree class. This method will check to see if the tree already has a root. If there is not a root, then put will create a new TreeNode and install it as the root of the tree. If a root node is already in place, then put calls the private recursive helper method put (with four parameters) to search the tree according to the following algorithm:
Starting at the root of the tree, search the binary tree comparing the new key to the key in the current node. If the new key is less than the current node, search the left subtree. If the new key is greater than the current node, search the right subtree.
When there is no left or right child to search, we have found the position in the tree where the new node should be installed.
To add a node to the tree, create a new TreeNode object and insert the object at the point discovered in the previous step.
Listing 6.14.6 shows the Java code for inserting a new node in the tree. The public put method with two arguments calls the he private put method, which is written recursively following the steps outlined above. Notice that when a new child is inserted into the tree, the currentNode is passed to the new tree as the parent.
One important problem with our implementation of insertion is that duplicate keys are not handled properly. As our tree is implemented, a duplicate key will create a new node with the same key value in the right subtree of the node having the original key. The result of this is that the node with the new key will never be found during a search. A better way to handle the insertion of a duplicate key is for the value associated with the new key to replace the old value. We leave fixing this bug as an exercise for you.
public void put(K key, V value) {
if (this.root != null) {
put(key, value, this.root);
} else {
this.root = new TreeNode(key, value);
}
this.size = this.size + 1;
}
void put(K key, V value, TreeNode currentNode) {
if (key.compareTo(currentNode.key) < 1) {
if (currentNode.leftChild != null) {
put(key, value, currentNode.leftChild);
} else {
currentNode.leftChild = new TreeNode(key, value,
currentNode);
}
} else {
if (currentNode.rightChild != null) {
put(key, value, currentNode.rightChild);
} else {
currentNode.rightChild = new TreeNode(key, value,
currentNode);
}
}
}
Listing6.14.6.The put Method
Note6.14.7.Java Note.
There are two methods named put, but Java does not have a problem with this because they have different method signatures: the method name, the number, and types of arguments. As long as these are different, there is no ambiguity when Java needs to figure out whch method to call. The return type and the access (public or private) are not part of the method signature.
Figure 6.14.8 illustrates the process for inserting a new node into a binary search tree. The lightly shaded nodes indicate the nodes that were visited during the insertion process.
Figure6.14.8.Inserting a Node with Key = 19
ExercisesSelf Check
1.
Which of the trees shows a correct binary search tree given that the keys were inserted in the following order 5, 30, 2, 40, 25, 4.
Remember, starting at the root keys less than the root must be in the left subtree, while keys greater than the root go in the right subtree.
good job.
This looks like a binary tree that satisfies the full tree property needed for a heap.
Subsection6.14.3Retrieving Values for a Key in a Binary Search Tree
Once the tree is constructed, the next task is to implement the retrieval of a value for a given key. The get method is less complex than the put method because it searches the tree recursively until it gets to a non-matching leaf node or finds a matching key. When a matching key is found, the value stored in the payload of the node is returned.
Listing 6.14.9 shows the code for get and the private get helper method. The search code in the helper method uses the same logic for choosing the left or right child as the put helper method. Notice that the get helper method returns a TreeNode to get, which allows the helper method to be used as a flexible method for other BinarySearchTree methods that may need to make use of other data from the TreeNode besides the payload.
public V get(K key) {
if (this.root != null) {
TreeNode result = get(key, this.root);
if (result != null) {
return result.value;
}
}
return null;
}
TreeNode get(K key, TreeNode currentNode) {
if (currentNode == null) {
return null;
}
if (key.compareTo(currentNode.key) == 0) {
return currentNode;
} else if (key.compareTo(currentNode.key) < 0) {
return get(key, currentNode.leftChild);
} else {
return get(key, currentNode.rightChild);
}
}
Listing6.14.9.The get Method
We can use the get helper method when implementing the containsKey method in Listing 6.14.10; if it returns a node, we return true; if it returns null, we return false:
public boolean containsKey(K key) {
TreeNode result = get(key, this.root);
return (result != null);
}
Listing6.14.10.The containsKey Method
Subsection6.14.4Displaying a Binary Search Tree
We would like to be able to see the resulting tree. Rather than display the tree graphically, we will instead display it as a nested list of the format:
[root [left tree] [right tree]]
Listing 6.14.11 shows the toString method with its stringify helper method, which does an inorder traversal of the tree.
public String toString() {
return stringify(this.root);
}
String stringify(TreeNode node) {
String result = "";
if (node != null) {
if (node.isLeaf()) {
result = " [" + node.key + "]";
} else {
result = " [" + node.key + stringify(node.leftChild) +
stringify(node.rightChild) + "]";
}
} else {
result = " []";
}
return result;
}
Listing6.14.11.Tree to String
At this point we have enough to implement a program to test our tree, shown in Listing 6.14.12:
This is a good time to take a break before proceeding to the remainder of this section.
Subsection6.14.5Iterating over a Binary Search Tree
Suppose that we would like to iterate over all the keys in the tree in order. You already know how to traverse a binary tree in order, using the inorder traversal algorithm. However, writing an iterator is a bit different since an iterator should return only one node each time it is called.
To make our iterator work, we will need two methods in the TreeNode class:
findSuccessor(node) takes a node as its argument and returns the next node with the next-largest key, called the successor. This will move us through the tree one node at a time.
findMinimumChild(node) returns the minimum key in a subtree whose root is the given node. We need this to find the smallest key in the tree as our starting point for the iterator, and also when finding a succesor.
Let’s address findSuccessor first. There are three cases to consider when looking for the successor:
If the node has a right child, then the successor is the smallest key in the right subtree.
If the node has no right child and is the left child of its parent, then the parent is the successor.
If the node is the right child of its parent, and itself has no right child, then the successor to this node is the successor of its parent, excluding this node.
TreeNode findSuccessor() {
TreeNode successor = null;
if (rightChild != null) {
successor = rightChild.findMinimumChild();
} else {
if (parent != null) {
if (isLeftChild()) {
successor = parent;
} else {
parent.rightChild = null;
successor = parent.findSuccessor();
parent.rightChild = this;
}
}
}
return successor;
Listing6.14.13.The findSucessor Method
Lines 3 and 4 handle the first case (there is a right child) by calling findMinimumChild. Line 7 tests to see if this node is a left child of its parent (the second case). Otherwise, we have the third case and this is the right child of its parent. Line 10 temporarily excludes this node from the tree, and line 12 retores the parent’s right child.
Listing 6.14.14 shows the code for finding the minimum child. You should convince yourself that the minimum value key in any binary search tree is the leftmost child of the tree. Therefore the findMinimumChild method follows the leftChild references in each node of the subtree until it reaches a node that does not have a left child. The code uses a while loop rather than using recursion to follow the left children:
TreeNode findMinimumChild() {
TreeNode current = this;
while (current.leftChild != null) {
current = current.leftChild;
}
return current;
}
Listing6.14.14.
Now that we have these methods, we have to modify the BinarySearchTree class. We change the first lines of the class to declare that this class is Iterable:
import java.util.Iterator;
public class BinarySearchTree<K extends Comparable<K>, V extends Comparable<V>>
implements Iterable<BinarySearchTree<K, V>.TreeNode> {
Our next step is to create an Iterator class that Java uses when it starts a for loop. (We can use it ourselves,too.)
class TreeIterator implements Iterator<BinarySearchTree<K, V>.TreeNode> {
TreeNode iteratorNode;
public TreeIterator() {
if (root.leftChild == null) {
iteratorNode = root;
} else {
iteratorNode = root.findMinimumChild();
}
}
public boolean hasNext() {
return iteratorNode != null;
}
public TreeNode next() {
TreeNode result = null;
if (iteratorNode != null) {
result = iteratorNode;
iteratorNode = iteratorNode.findSuccessor();
}
return result;
}
}
Listing6.14.15.Initializing an Iterator
Line 2 creates a TreeNode that keeps track of where we are in the tree.
The constructor is in lines 4–10. It sets the iteratorNode to the first (smallest) element in the tree. If the root doesn’t have a left child, then the root must be the smallest element, as everything to the right of the root is larger than the root. Otherwise, if there is a left child, we must find its minimum child in line 8.
We now implement two methods used by the iterator. hasNext in lines 12–14 returns true if there is a next node; false otherwise—this is used to decide when to end a loop using the iterator. The next method in lines 16–23 moves the iterator to the successor node (or null if we have finished traversing the tree) and returns it.
At last! We can now write the program in Listing 6.14.16 that tests insertion, accessing nodes, and traversal of a binary search tree. In lines 18–21 we iterate through the tree with a for loop; in lines 25–31 we set up an iterator of our own for use with a while loop.
Listing6.14.16.Using the Binary Search Tree
In line 18, we must use the fully qualified class name BinarySearchTree.TreeNode because the TreeNode class is nested inside the BinarySearchTree class. In line 25, we must also add the data types for the key and value.
Subsection6.14.6Removing a Key from a Binary Search Tree
Finally, we turn our attention to the most challenging operation on the binary search tree, the deletion of a key (see Listing 6.14.17). The first task is to find the node to delete by searching the tree. If the tree has more than one node we search using the get method to find the TreeNode that needs to be removed. If the tree only has a single node, that means we are removing the root of the tree, but we still must check to make sure the key of the root matches the key that is to be deleted. In either case, if the key is not found the remove method raises an error.
public TreeNode removeKey(K key) {
if (size > 1) {
TreeNode nodeToRemove = get(key, root);
if (nodeToRemove != null) {
removeNode(nodeToRemove);
size = size - 1;
return nodeToRemove;
} else {
throw new NoSuchElementException(
key.toString() + " not in tree.");
}
} else if (size == 1 && root.key.equals(key)) {
root = null;
size = size - 1;
return null;
} else {
throw new NoSuchElementException(
key.toString() + " not in tree.");
}
}
void removeNode(TreeNode currentNode) {
// to be determined...
}
Listing6.14.17.
Once we’ve found the node containing the key we want to delete, there are three cases that we must consider:
The node to be deleted has no children (see Figure 6.14.18).
The node to be deleted has only one child (see Figure 6.14.19).
The node to be deleted has two children (see Figure 6.14.20).
Figure6.14.18.Deleting Node 16, a Node without Children
Figure6.14.19.Deleting Node 25, a Node That Has a Single Child
Figure6.14.20.Deleting Node 5, a Node with Two Children
The first case is straightforward. If the current node has no children, all that has to happen is to delete the node and remove the reference to this node in the parent. The code for this case is shown in Listing 6.14.21.
if (currentNode.isLeaf() {
if (currentNode == currentNode.parent.leftChild) {
currentNode.parent.leftChild = null;
} else {
currentNode.parent.rightChild = null;
}
}
Listing6.14.21.Removing a Leaf Node
The second case is only slightly more complicated. If a node has only a single child, then we promote the child to take the place of its parent. The code for this case is shown in Listing 6.14.24. As you look at this code, you will see that there are six cases to consider. Since the cases are symmetric with respect to either having a left or right child, we will just discuss the case where the current node has a left child. The decision proceeds as follows:
If the current node is a left child, then we need to update the parent reference of the left child to point to the parent of the current node, and then update the left child reference of the parent to point to the current node’s left child.
If the current node is a right child, then we need to update the parent reference of the left child to point to the parent of the current node, and then update the right child reference of the parent to point to the current node’s left child.
If the current node has no parent, it must be the root. In this case we will replace the key, value, leftChild, and rightChild data by calling the replaceValue method on the root.
Figure 6.14.22 shows before-and-after diagrams of these three situations.
Figure6.14.22.Removing a Node with One Child
In Listing 6.14.23, we have implemented a method named adjustParent to take care of the symmetric situations without having to duplicate code. It adjusts the relationships between the child of the node we want to remove and the parent of the node we want to remove.
We use this method in the portion of removeKey that handles nodes with one child. The code fragment is shown in Listing 6.14.24.
else { // case 2: one child only
if (currentNode.leftChild != null) {
adjustParent(currentNode, currentNode.leftChild);
}
else {
adjustParent(currentNode, currentNode.rightChild);
}
}
Listing6.14.24.Removing a Node with One Child
The third case is the most difficult case to handle. If a node has two children, then it is unlikely that we can simply promote one of them to take the node’s place. We can, however, search the tree for a node that can be used to replace the one scheduled for deletion. What we need is a node that will preserve the binary search tree relationships for both of the existing left and right subtrees. The node that will do this is the node that has the next-largest key in the tree. This is the successor node, and we already know how to find the successor—we used it for our iterator in Listing 6.14.13.
The successor is guaranteed to have no more than one child, so we know how to remove it using the two cases for deletion that we have already implemented. Once the successor has been removed, we put it in the tree in place of the node to be deleted. The code to handle the third case is shown in Listing 6.14.25.
In Listing 6.14.25 we make use of the helper methods findSuccessor and spliceOut to find and remove the successor. The reason we use spliceOut is that it goes directly to the node we want to splice out and makes the right changes. We could call remove recursively, but then we would waste time searching again for the key node. The code goes after the code for removing a node with no children.
} else if (currentNode.hasChildren()) { // case 3: two chilren
TreeNode successor = currentNode.findSuccessor();
successor.spliceOut();
currentNode.key = successor.key;
currentNode.value = successor.value;
}
Listing6.14.25.
The code for splicing out shown below (see Listing 6.14.26), and it is a method of the TreeNode class. This code makes use of the same properties of binary search trees that cause an inorder traversal to print out the nodes in the tree from smallest to largest.
