Fill in the following chart with the times in nanoseconds measured. You may need to adjust the values of n according to your platform. That is, if your program takes too long to complete, or if you run out of memory, etc., reduce the range of n as needed. If on the other hand, your program completes the execution very fast, increase the range of n as much as possible to observe behavior for large n. In any case, make sure you have at least 5 columns of data. (No points if you have less than 4 columns of data.)

search	n = 102	n = 103	n = 104	n = 105	n = 106
Balanced BST (nanosecs)

Explain how the growth of these measurements compare with your big-O running time. If your measurements do not match your conjecture, investigate the reason by looking carefully at the code of the BST class, and explain what happened. (No points if you do not say something like when n is multiplied by xxx the running time is yyy. Partial points if your measurements do not match and you say it, but you do not explain what you did to investigate the reason.)

/** * Exception class for access in empty containers * such as stacks, queues, and priority queues. * @author Mark Allen Weiss */ public class UnderflowException extends RuntimeException { }

// BinarySearchTree class // // CONSTRUCTION: with no initializer // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x // boolean contains( x ) --> Return true if x is present // Comparable findMin( ) --> Return smallest item // Comparable findMax( ) --> Return largest item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // void printTree( ) --> Print tree in sorted order // ******************ERRORS******************************** // Throws UnderflowException as appropriate

/** * Implements an unbalanced binary search tree. * Note that all "matching" is based on the compareTo method. * @author Mark Allen Weiss */ public class BinarySearchTree> { /** * Construct the tree. */ public BinarySearchTree( ) { root = null; }

/** * Insert into the tree; duplicates are ignored. * @param x the item to insert. */ public void insert( AnyType x ) { root = insert( x, root ); }

/** * Remove from the tree. Nothing is done if x is not found. * @param x the item to remove. */ public void remove( AnyType x ) { root = remove( x, root ); }

/** * Find the smallest item in the tree. * @return smallest item or null if empty. */ public AnyType findMin( ) { if( isEmpty( ) ) throw new UnderflowException( ); return findMin( root ).element; }

/** * Find the largest item in the tree. * @return the largest item of null if empty. */ public AnyType findMax( ) { if( isEmpty( ) ) throw new UnderflowException( ); return findMax( root ).element; }

/** * Find an item in the tree. * @param x the item to search for. * @return true if not found. */ public boolean contains( AnyType x ) { return contains( x, root ); }

/** * Make the tree logically empty. */ public void makeEmpty( ) { root = null; }

/** * Test if the tree is logically empty. * @return true if empty, false otherwise. */ public boolean isEmpty( ) { return root == null; }

/** * Print the tree contents in sorted order. */ public void printTree( ) { if( isEmpty( ) ) System.out.println( "Empty tree" ); else printTree( root ); }

/** * Internal method to insert into a subtree. * @param x the item to insert. * @param t the node that roots the subtree. * @return the new root of the subtree. */ private BinaryNode insert( AnyType x, BinaryNode t ) { if( t == null ) return new BinaryNode( x, null, null ); int compareResult = x.compareTo( t.element ); if( compareResult < 0 ) t.left = insert( x, t.left ); else if( compareResult > 0 ) t.right = insert( x, t.right ); else ; // Duplicate; do nothing return t; }

/** * Internal method to remove from a subtree. * @param x the item to remove. * @param t the node that roots the subtree. * @return the new root of the subtree. */ private BinaryNode remove( AnyType x, BinaryNode t ) { if( t == null ) return t; // Item not found; do nothing int compareResult = x.compareTo( t.element ); if( compareResult < 0 ) t.left = remove( x, t.left ); else if( compareResult > 0 ) t.right = remove( x, t.right ); else if( t.left != null && t.right != null ) // Two children { t.element = findMin( t.right ).element; t.right = remove( t.element, t.right ); } else t = ( t.left != null ) ? t.left : t.right; return t; }

/** * Internal method to find the smallest item in a subtree. * @param t the node that roots the subtree. * @return node containing the smallest item. */ private BinaryNode findMin( BinaryNode t ) { if( t == null ) return null; else if( t.left == null ) return t; return findMin( t.left ); }

/** * Internal method to find the largest item in a subtree. * @param t the node that roots the subtree. * @return node containing the largest item. */ private BinaryNode findMax( BinaryNode t ) { if( t != null ) while( t.right != null ) t = t.right;

return t; }

/** * Internal method to find an item in a subtree. * @param x is item to search for. * @param t the node that roots the subtree. * @return node containing the matched item. */ private boolean contains( AnyType x, BinaryNode t ) { if( t == null ) return false; int compareResult = x.compareTo( t.element ); if( compareResult < 0 ) return contains( x, t.left ); else if( compareResult > 0 ) return contains( x, t.right ); else return true; // Match }

/** * Internal method to print a subtree in sorted order. * @param t the node that roots the subtree. */ private void printTree( BinaryNode t ) { if( t != null ) { printTree( t.left ); System.out.println( t.element ); printTree( t.right ); } }

/** * Internal method to compute height of a subtree. * @param t the node that roots the subtree. */ private int height( BinaryNode t ) { if( t == null ) return -1; else return 1 + Math.max( height( t.left ), height( t.right ) ); } // Basic node stored in unbalanced binary search trees private static class BinaryNode { // Constructors BinaryNode( AnyType theElement ) { this( theElement, null, null ); }

BinaryNode( AnyType theElement, BinaryNode lt, BinaryNode rt ) { element = theElement; left = lt; right = rt; }

AnyType element; // The data in the node BinaryNode left; // Left child BinaryNode right; // Right child }

/** The tree root. */ private BinaryNode root;

// Test program public static void main( String [ ] args ) { BinarySearchTree t = new BinarySearchTree( ); final int NUMS = 4000; final int GAP = 37;

System.out.println( "Checking... (no more output means success)" );

for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) t.insert( i );

for( int i = 1; i < NUMS; i+= 2 ) t.remove( i );

if( NUMS < 40 ) t.printTree( ); if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 ) System.out.println( "FindMin or FindMax error!" );

for( int i = 2; i < NUMS; i+=2 ) if( !t.contains( i ) ) System.out.println( "Find error1!" );

for( int i = 1; i < NUMS; i+=2 ) { if( t.contains( i ) ) System.out.println( "Find error2!" ); } } }