16.7: The Binary Search Tree Data Structure

To gain some appreciation of what binary search trees are and why they are useful in implementing the Set and Map interfaces, let’s make a few comments about implementing very simple versions of these structures.

Like a linked list, a binary tree is a data structure consisting of a collection of nodes that are linked together by references from one node to another. However, unlike a linked list, each node in a binary tree contains references to two other other nodes, (left and right), corresponding to the left- and right-subtrees growing out of a particular node. A subtree is a tree that is part of larger tree. This creates a tree-like structure, as shown in Figure 16.36. Note that some of the references to other nodes might be null. The trunk of the tree corresponds to the node labeled root. In computer science, trees are almost always drawn upside down. Thus the trunk of the tree, root, is at the top of the figure.

If we assume that the objects contained in a tree are from a class that implements the Comparable interface, then a binary search tree is a binary tree in which the objects are ordered so that the object at a particular node is greater than the objects stored in its left subtree and less than the objects stored in its right subtree.

Figure 16.36 shows a binary search tree with the phone list data that we have used throughout the chapter. Objects are compared by comparing the names alphabetically. From the figure it is easy to see that searching for a object should start at the root of the tree. At each node, examining the name at the node will tell you whether you have found the object there. Otherwise, by checking the name at the node, you can decide which subtree the data could be in, and you can traverse either left or right through each level of the tree. One can deduce that if the tree is balanced—that is, if at most nodes the size of the left subtree is about the same size as the right subtree—searching the tree much faster than searching a linked list.

Figure 16.36: A binary search tree of PhoneTreeNodes.

This is one of the main advantages of using a binary search tree over a linked list.

The TreeSet and TreeMap classes implement sophisticated algorithms for inserting and removing data from a tree, which guarantees that the tree remains relatively balanced. The details of these algorithms are beyond the scope of this book, but would be a subject of study in a standard Data Structures and Algorithms course.

We will conclude this subsection by giving a brief outline of an implementation of a simple binary search tree that stores our phone list data. Like our LinkedList example, you need to define a node class and a tree class. The node class with unimplemented methods, would look like:

public class PhoneTreeNode {

private String name;

private String phone;

private PhoneTreeNode left;

private PhoneTreeNode right;

 

public PhoneTreeNode (String nam, String pho ){}

public void setData (String nam, String pho){}

public String getName (){}

public boolean contains (String nam, String pho ){}

public void insert(String nam, String pho ){}

//other methods

} //PhoneTreeNode

The tree structure itself contains a reference to a node:

public class PhoneTree {

private PhoneTreeNode root;

 

public PhoneTree(){}

public boolean contains (String nam, String pho ){}

public void insert(String nam, String pho){}

// other methods

} //PhoneTreeNode

We will implement only the two contains() methods. The PhoneTree version is very simple:

public boolean contains (String nam, String pho){

if (root == null) return false;

else return root.contains(nam, pho);

} // contains () in PhoneTree

 

The implementation of the contains() method of PhoneTreeNode is only slightly more involved.

public boolean contains (String nam, String pho){

if (name.equals(nam))

return true;

else if (name.compareTo(nam)<0){ //name < nam

if (right == null) return false;

else return right.contains (nam, pho);

} else {{\color {cyan} //name > nam}

if(left == null) return false;

else return left.contains (nam, pho);

}

} // contains () in PhoneTreeNode