UNC-CH COMP 410

Binary Search Tree Implementation

Basic Binary Search Tree (BST)

You will write code that implements, exercises, and analyzes binary search trees. We are eventually going to build splay trees but will get there one chunk at a time, and the first chunk is the basic BST. There are plenty of implementations of "tree" stuff out there. Please do not copy those. I want you to write your own code. The learning in this activity comes from actually powering through all the reasoning needed to get the pointers (objects) and recursive calls hooked up correctly.

What to Hand-in

Hand in your code as per the instructions under Assignment 3 in Sakai.

Submit a single text file containing the entire Java source... main driver class, random and keyboard code as needed, as well as BST classes. Basically, the text should be all source code needed to compile and run your program. Please check it once you have made the file, to make sure it is self contained and does compile and execute. Remember, to make this work, leave the modifier "public" off of your class declarations.

Program Source text organization

Please name your main class "Assn3Main" and organize your single text source file this way:

   class Assn3Main {
     public static void main (String[] args) {
        // in here code for doing the 
        // interactive builder/tester mode
        // and the command line arg auto-execution mode
     }
   }

   // then classes for the BST itself

   // then supporting classes for random data, 
   // etc.

Details

BST first

You can get started by writing a class that implements a Binary Search Tree (BST). Make the tree contain string values. You may do this with generics, or you may do it by writing the classes to use String directly. Both are fine.

Your BST should contain the following operations (with these names and signatures):


  Name the class BST

  new       :          -->  BST
  insert    :  String  -->      (or maybe a boolean showing success)
  remove    :  String  -->      (or maybe a boolean showing success)
  findMin   :          -->  String
  findMax   :          -->  String
  contains  :  String  -->  boolean
  get       :  String  -->  TreeNode
  val       :          -->  String  (returns the key stored in the root)
  empty     :          -->  boolean
  size      :          -->  int+ (an integer zero or larger)
  height    :          -->  int+ (an integer zero or larger)

You can implement your tree code iteratively or recursively. You may use the code in the book as a guide, but as noted, do not modify and submit online implementations as your code.

The "get" operation may need an explanation. What get should do is locate the key value in the BST, and if it is found, return a reference to the tree cell containing that key value. This will be a tree cell object, not a complete BST. Your BST will be an object that contains a reference to s root cell, and perhaps some other variables needed to make the BST provide the requested info. What "get" returns is the same thing as the reference to the root cell... a single node from the tree.

Input/Execution Modes and Run Arguments

The program will comprise the basic BST classes with a main driver that has two modes. One mode interacts with the user to get operations and data to perform. It will loop until the user indicates to stop. Make one of the possible user selections be to print out the tree. If you wish you can make one of the user selections also be to put some amount of random string data into the tree. The other mode reads the command line parameters (like in Assn 2) and non-interactively executes the operations requested there.

You may find this code useful. It shows how to do run arguments (command line arguments) in Java, and how to detect if there are no such arguments. In this program you will need to detect the presence or absence of run arguments. If there are no run args then your main will enter an interactive test driver that will allow manually building and manipulating a BST. If there are run args, your program will instead read those arguments (strings) as command as data for the commands, and will make your BST ADT do those commands.

Driver/tester main method

As with the Bridge Queue, make the main method be a test driver. This test driver will be interactive, requesting keyboard input from the user (see keyboard code below). It basically will be a big loop, asking for an operation to do on a tree, doing it, and going back for more (until the user says stop). In this loop it will first ask the user what operation to perform. Based on what the user selects, it may then have to get more input from the user. Following the BST ADT signature given in the powerpoint slides, it should provide these operations:

new: make a new empty tree
i: insert a string (get the value from the user)
r: remove a node containing a string (remove it from the tree)
c: contains a string (return and report a boolean indicating success)
g: get a node that has a string as value
x: findMax, returns a string
n: findMin, returns a string
v: val, gets the value stored in the root node
e: empty
s: size
h: height
q: quit the tester loop
p: print the tree for inspection (see below)
f: (optional) fill the tree with some amount of random string data (see random code below)

Make your driver accept the short character strings shown as commands so there is less typing for the user to do. You can have your BST and your driver do more ops/things if you wish, but I want to see these at least so I can count on them being there and named this way when i test.

The size operation tells how many elements are stored in the BST. The height operation tells the length of the longest path from root to a leaf. The get operation returns a link (pointer) to the node that contains the String sent as parameter; if the string is not in the BST it returns null. The insert operation should do nothing if the string being inserted is already in the tree (we will assume unique key values); if you are implementing it to return a boolean then it can return false if the insert is not done and true if the string is successfully added to the BST. The remove operation can be similar; if the item to be removed it not in the BST do nothing (and perhaps return false), and if it is there remove it (and perhaps return true). Note on optional random fill: We will be generating random string data for the next assignment (balanced trees). If you wish to go ahead and get that functionality working now, it may help you in testing your BST code without typing a lot of strings at the keyboard.

Tree Print method

Write a method to allow the tree contents to be printed to see its structure visibly. You may not wish to run this method on large trees, but it will be useful in debugging your code on small trees.

To print a tree, lets do something simple. Let's make print a recursive method, and make it traverse the tree using one of two traversal orders (your choice). Examples of each are shown below for a small binary search tree. Make your choice based on which approach produces a print form that helps you see the tree structure most clearly.

pre-order: This means the root will be the first thing printed, then the entire left child subtree (with its root first etc.) then the entire right subtree. Use indentation to show levels; this means when you print the root of a subtree, indent it a few spaces more than its parent node. Feel free to decorate your printing in any way you like to help the reader to see the tree structure.

reverse in-order: In this case, you do an in-order traversal, but you visit the right subtree before the left. Use indentation to show levels. This form will generate a tree that, if you tilt your head to the left, will look "tree like" and you may find it easier to see the structure for testing purposes.

example: reverse in-order

         weathervane
    stovepipe
         pattern
machine
         jackstand
    garage
         airplane

example: pre-order

machine
  garage
    airplane
    jackstand
  stovepipe
    pattern
    weathervane

Supporting Code Examples

Random strings

You may find this code useful. It is a class that generates random strings of characters from "a" to "z". It will generate strings that are 5 to 25 characters in length by default if you call MyRandom.nextString() with no arguments. If you wish to control the string lengths better, then you can call it with arguments. Calling MyRandom.nextString(3,11) for example will generate string that vary in length from 3 to 11 characters. The nextString methods are declared static so you can call them as shown with the class name qualifier and don't need to instantiate an object in your code.

Keyboard input

You may find this code useful. You will be writing an interactive test "driver" to build and exercise the tree; it will take commands from the user at the keyboard. The sample code shows one way to do keyboard input in Java. Another way is to use the Scanner class, which wraps the various streams shown in the sample code. It is even simpler to use. Scanner includes methods like "next" and "nextLine" to get the next String, or an entire line of text (to the return key), as well as methods like "nextInt" and "nextFloat" to parse various types from the input text directly. Here is a code example.