Section 16.8. The Binary Search Tree Data Structure

[Page 799 (continued)]

16.8. The Binary Search Tree Data Structure

To provide some appreciation of what binary search trees are and why they are useful in implementing the Set and Map interfaces, we will briefly discuss 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 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 may 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.

Figure 16.36. A binary search tree of PhoneTreeNodes.

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 any given 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 balancedthat is, if at most nodes the size of the left subtree is about the same size as the right subtreesearching the tree would be much faster than searching a linked list. This is one of the main advantages of using a binary search tree over a linked list.

---

[Page 800]

The TReeSet and treeMap classes implement sophisticated algorithms for inserting and removing data from a tree. These algorithms guarantee that the tree remains relatively balanced. The details 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 class 

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 class 

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.

---

[Page 801]

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 {                                   // name > nam         if (left == null) return false;         else return left.contains(nam, pho);     } } // contains() in PhoneTreeNode