Computer Science Project

1

COMP 182 Fall 2016

Project 6 Binary Search Trees

You will implement a container for integer values using a Binary Search Tree for the underlying data

structure. The operations or features that your container will support are

Data Management

 insert (or add or put)

 delete (or remove)

 find (or lookup or get)

 traversal (or show)

I/O

 generate (random number generation)

 array input/output (conversion from/to array)

 file input/output (read/write)

 menu (for command-line interaction with user)

interface IBST {

public void insert(int v);

public boolean delete(int v);

public boolean find(int v);

}

class Node {

public int data;

public Node left, right;

// other methods if you want …

}

class MyTree implements IBST {

private Node root;

public MyTree() { … }

public MyTree(int[] x) { … }

public void insert(int value) { … }

public boolean delete(int value) { … }

public boolean find(int value) { … }

public int getHeight(boolean output) { … }

public boolean confirm() { … }

public String toString() { … }

public String toString(String type) { … }

public void show() { … }

public void show(String type) { … }

private String inOrder() { … }

private String preOrder() { … }

private String postOrder() { … }

public void menu() { … }

}

2

Menu

Write the menu method to support the following options:

generate 20 1000 // fills tree with random numbers

insert 37 // inserts value

delete 23 // tries to delete, prints “okay” or “not found”

find 92 // tries to find, prints “found” or “not found”

show // by default, shows inorder traversal

show inorder // shows inorder traversal

show preorder // shows preorder traversal

show postorder // shows postorder traversal

confirm // confirms that tree satisfies the BST property (for testing)

// also prints performance info: # nodes, log2(# nodes), height

Performance Measures for BST

The performance of the BST depends on how “flat” and short the tree becomes due to insertions and

deletions. A flat short tree can be searched quickly, a tail skinny tree takes longer. Equivalently, we could

say that performance depends on how balanced or unbalanced the tree is. A flat short tree is relatively

balanced, a tall skinny tree is relatively unbalanced. We can get a good estimate how balanced a tree is at

any time by observing or measuring three values:

 Total Number of Nodes in the BST

 Average Number of Nodes on Any Path from Root to Leaf

 Height (Maximum Number of Nodes on Any Path from Root to Leaf) In the best case, the height will equal log2(# nodes), and the typical operation will have complexity O(log

n). In the worst case, the height equals the number of nodes, and the typical operation will have complexity

O(n). In the worst case, the performance of the BST is the same as the performance of the linked list.

Recursive or Iterative Methods?

With BSTs, many methods can be implemented in either a recursive or iterative style. For some methods,

one style will seem more natural than the other. I encourage you to try both for such methods as insert(),

delete(), or find(). For example, here’s one way to implement your code to allow you to try different

implementations and switch between them. This is the example for the insert() method, other methods

could be handled similarly.

private static boolean recursive;

public static void setRecursive(boolean f) { recursive = f; }

public void insert(int value) {

if (recursive) insert_r(value);

else insert_i(value);

}

private void insert_r(int value) { … }

private void insert_i(int value) { … }

Add a method setRecursive() to change the style between recursive and iterative. Call this method from

your driver during testing or demonstration.

Only make these modifications after you have completed basic working versions of insert, delete, and find.

You can also try this for the traversal methods inOrder, preorder, and postOrder, but in this case you’ll

probably find the recursive versions much more natural and simple.

3

Testing

As before, create a Driver class with a main method that acts as a testing script. For initial testing, the

menu method will be the most helpful.

MyTree t = new MyTree();

t.menu();

For later testing, streamline the script to handle larger amounts of data, with a simple confirmation.

MyTree t = new MyTree();

t.generate(20,1000);

t.show();

or MyTree t = new MyTree();

t.generate(100000,1000000);

t.confirm();

or int[] x = new int[1000];

[fill x with random numbers]

MyTree t = new MyTree(x);

…

Also, try creating an extended script and use I/O redirection.

Driver: MyTree t = new MyTree();

t.menu();

Script Stored in script.txt File:

insert 345

insert 2946

insert 104

…

delete 2465

…

show

To Run From Terminal Command Line: % java Driver < script.txt

4

GUI Tree Display

Included below is a Java class named TreeDisplay to display a MyBST to the desktop using features of the

Java graphical user interface (GUI) packages. This is simply for testing purposes, to help you visualize the

BST being manipulated by your code.

For example, here is a trace of the building of a MyTree with 20 nodes:

Values inserted:

554 575 175 741 249 287 272 289 59 27 807 404 109 636 193 241 543 206 313 695

TreeDisplay GUI:

Note that the left child node is displayed as the first child, and the right child node is displayed as the

second child. In the case that a node has a right child but no left child, a special null node is inserted into

the left child position. For example, see node 636 in the tree above.

To use from a test script: MyTree tree = new MyTree();

tree.insert(…);

tree.insert(…);

DisplayTree.show(tree);

5

Complete Code for TreeDisplay.java

import java.awt.*;

import java.awt.event.*;

import javax.swing.*;

import javax.swing.tree.*;

public class TreeDisplay extends JPanel {

private DefaultMutableTreeNode root;

private JTree jtree;

private MyBST tree;

private DefaultMutableTreeNode nullnode;

public TreeDisplay(MyBST tr) {

tree = tr;

root = buildJTree();

jtree = new JTree(root);

this.add(jtree);

}

private DefaultMutableTreeNode buildJTree() {

nullnode = new DefaultMutableTreeNode();

nullnode.setUserObject("null");

return buildJTree(tree.root);

}

private DefaultMutableTreeNode buildJTree(Node n) {

if (n==null) return null;

DefaultMutableTreeNode tn = new DefaultMutableTreeNode();

tn.setUserObject(new Integer(n.value));

if (n.left==null && n.right != null) {

tn.add(nullnode);

}

if (n.left != null) {

tn.add(buildJTree(n.left));

}

if (n.right!=null) {

tn.add(buildJTree(n.right));

}

return tn;

}

public static void show(MyBST tr) {

TreeDisplay treepanel = new TreeDisplay(tr);

JScrollPane jsp = new JScrollPane(treepanel);

JFrame f = new JFrame("BST Displayer");

f.setContentPane(jsp);

f.setSize(100,300);

f.setVisible(true);

}

}