The way that data is stored in a Binary Search Tree (BST) depends on the order in which the values are inserted. For example, if we insert the numbers 1, 2, 3 in that order, the resulting tree has 1 in the root, 2 as a right child of the root, and 3 as a right child of 2. However, if we insert first 2, then 2 will be stored in the root, and 1 and 3 will be the left and right child of the root respectively. Moreover, not only the values are stored in different places but also the shape of the tree obtained is different. The first one is skewed whereas the second one is balanced. As a consequence, although both trees contain the same data, the worst-case cost of searching differs. The purpose of this assignment is to highlight this striking difference in running time, creating a skewed BST and a (roughly) balanced BST, both with a large number of nodes, and measuring the execution time of searching on each

Write a program to do the following.

Input an integer x. (Should work with big numbers.)

Create a completely-skewed BST S containing 1, 2, . . . , x.

Create a BST R containing x integers without repetitions generated at random. (To minimize the risk of repetitions, you can multiply the value returned by random() by a big number.) Given that the numbers are generated uniformly at random, the tree will likely be balanced.

Measure the time to search in S for a number that is not in the tree.

Can you please guide me on this ?

------------------------------------------------------------------------------------------------

Also, how can I test it in the below code?

:

// 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!" ); } } }