Lab 6: Binary Search Trees

Copyright RIT 2008
$Id: writeup.xml,v 1.11 2010/04/16 13:04:36 vcss233 Exp $

Goal

  1. Write a generic binary tree node class.
  2. Complete the implementation of a generic binary search tree, which uses the binary tree as the data structure.
  3. Write recursive solutions for determining the height and size of a tree.
  4. Write a recursive solution for finding whether an item is in the tree.
  5. Write a recursive inorder traversal method.
  6. Run tests to determine the number of comparisons made while searching for an item.

Overview

In this lab, you will write a complete binary tree node class and complete a binary tree implementation. The methods in the tree class will allow you to build the tree, query its height and size, perform an inorder traversal, and search for elements. You will also determine the performance of the binary tree using different input sets.

Pre - Lab Work

  1. Review your course notes on binary search trees.

  2. (Lecture) Read Goodrich, Chapter 7.3.

  3. (Studio) Read Liang, Chapter 25.

  4. Read the tutorial on Java Generics (http://java.sun.com/j2se/1.5.0/docs/guide/language/generics.html) .

In-Lab Activities

In the first activity, you will implement a generic binary tree node class, and in the second activity you will complete implementation of a binary tree class which uses the node class. For the third activity you will evaluate the performance of several different trees.

Download a copy of the jar file: lab6.jar (http://www.cs.rit.edu/~vcss233/pub/lab06/Binaries/lab6.jar) that contains the files you need to complete this lab and unpack it in your CS3 lab subdirectory.

Activity #1 : Write a Generic Binary Tree Node Class

Create a new file, BTNode.java to contain the implementation of the node class. Read the javadoc for the BTNode. This is a generic class: BTNode<T>. When a class is generic, the creator of an instance of that class supplies a type for that class to use. These examples supply String and Integer to the constructor and to the type declaration: 


BTNode< String> nodeString = new BTNode<String>("string");
BTNode<Integer> nodeInt = new BTNode<Integer>(10);

Within the BTNode class, T is the name of the generic type supplied by the creator of the node instance. Internally, the node class uses T as the name of the type of data element stored in the node. Generics allow you to write one node class that can work with any data type and is guaranteed to be "type safe".

Since the BTNode class has more than one constructor, you might think you have to write the same thing twice; think again. You should use the this() construct in one constructor to chain it to the other. That way a constructor can reuse the code from the other constructor.

In the jar file, you will find the file BTNodeTest.java. The BTNodeTest class is a test program to verify your BTNode class. After you have written the BTNode class, you must test it using the supplied BTNodeTest.java file. This class contains a main method that creates a variety of BTNode objects of different types. It checks that all the data members and all the methods in the BTNode class are correct.

How To Submit

When you are sure that your node class is working properly, submit your work by executing the following command: 


try grd-233 lab6-1 BTNode.java

Activity #2 : Implement a Binary Search Tree

How (NOT) to use Generics

Many developers forget to specify the generic type when they construct an instance of a generic class. Although incorrect, this statement compiles and runs: 


BTNode node = new BTNode("string");

In the above case, BTNode treats the generic type, T, to be of type Object, even though it received a String object reference. Compiling this statement will produce the following warning: 


% javac Client.java
Client.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Recompiling with the -Xlint:unchecked option will identify the unchecked code: 


% javac -Xlint:unchecked Client.java
Client.java:  warning: [unchecked] unchecked call to BTNode(T) as
a member of the raw type BTNode
BTNode node = new BTNode("string");
              ^

If you forget to specify the type for the generic tag, the client must typecast whenever accessing elements from the node, like this: 


String str = (String) node.getData();

Also, there is no way to protect from a ClassCastException exception at run time such as here: 


	Integer i = (Integer) node.getData();

MORAL : always supply a type when creating generic objects.

Your Java code should always compile cleanly without warnings.

Binary Search Tree Implementation

In this activity you will complete the implementation of the binary search tree class, BST, finishing the code supplied in the file BST.java.

The BST class uses the BTNode class from the previous activity. There is also another test program: BSTTest.

The BST class implements a binary search tree, whose nodes are BTNode objects. The BST class stores the root node of the tree as a data member.

Notice the methods you will be implementing follow a pattern. The BST class already contains stubbed methods to insert elements into the tree. Clients call a public insert method to insert a data element into the tree, and the public method calls a private insert method to recursively traverse and insert the data element. The private method hides the root from the client and keeps the underlying BTNode class hidden.

The first task is to write the inorder traversal method. Recall that an inorder traversal visits the left node, followed by the current node, and then the right node. At each node, you should print its data element to standard output. Print each node using its toString() method, with one node per line.

To test your traversal, compile and run the BSTTest program and specify an input file. There are three test files provided in the jar file: input1, input2, input3. The test program assumes the data is a series of integers. To run with file input1, do the following: 


java BSTTest input1

The test program reads the data from the file, prints the size and height of the tree, and performs an inorder traversal printing each node value on a separate line. Make sure the printed order is correct based on the input file and your understanding of how a binary search tree is built.

At this point the test program expects you to enter values to insert into the tree. You should enter ctrl-d for now. Finally, it searches for every single element in the tree and reports some statistics (which should all be zero).

The next task after you have produced a correct traversal, is to write the size and height methods. BOTH of these methods must be written recursively. The size of the tree is the number of nodes in the tree.

The height of the tree is the number of arcs, or paths, from the root of the tree to the deepest node in the tree. A tree that has no nodes has a height of -1. See the javadoc comments on these methods.

The last task is to implement the find methods. The public find method must call the private find method with the data element to find and the root of the tree. When searching at a node in the tree, you must compare the data element to find to the current node's data using the compareTo method. If you are comparing the data to find to the current node's data, the result of compareTo will indicate whether to branch to the left (less than 0), branch to the right (greater than 0), or stop because the element is found (equals 0). That is why the signature of the BST class is: 


public class BST <T extends Comparable<T>>

The above class declaration tells the compiler that the data type of all elements in the tree must be comparable to each other using compareTo.

Each time the program makes a comparison (once per node visited), the program must increment the numCompares data member.

How To Submit

When you are sure that your binary search tree is working properly, submit your work by executing the following command: 


                try grd-233 lab6-2 BTNode.java BST.java

Activity #3 : Comparing Binary Search Tree Performance

For the final activity you will answer questions in the supplied act-questions.txt file. You will use the binary search tree to analyze the performance of the two trees created by the input files input2 and input3.

Study both of these input files and determine what kind of tree will be created by each. You will run BSTTest.java on each and record statistics such as the height and size of each tree, as well as the number of comparisons it takes to find elements.

Using your knowledge of time complexity you will categorize the search times of each of the trees and explain what the relationship between the height of a tree and its search time is. Express your complexity measurements in terms of N, the number of nodes in the tree.

How To Submit

Submit your answer file using: 


                try grd-233 lab6-3 act-questions.txt

Grade Computation

Grade Breakdown: