This time we want to measure the performance of a Binary Search Tree, compared t

Question

This time we want to measure the performance of a Binary Search Tree, compared to a Linked List, with the following benchmark tests:

Test 1:

? Create an array int[] INPUT of n random integer numbers between 0 and 2n, delete the numbers that occur more than one time, and store the remaining set of unique numbers in an array int[] OUTPUT.

? For comparison, do this using a LinkedList (java.util.LinkedList), then use an ArrayList (java.util.ArrayList) instead, finally utilize a BST (my implementation).

? Compare the runtime for the three data structures and multiple, appropriate n (if you use a number n which is too small, the runtime will be 0 all time: that's not a valid result.)

? Comment (.doc or .pdf document) on the results: create a table of the results (by hand, not automatically), compare the numbers to the expected runtime performance (O(..?..)), and explain the result.



Test 2: Use the array OUTPUT (the one with unique numbers)

? Sort the array in the following ways and compare the performance:

? First use a LinkedList. Sort by? iteratively finding and deleting the minimum of the (remaining) numbers.

? Then use a Binary Search Tree: again, do the routine: find the minimum and delete it. You have to add a method 'delete' to my BST code in order to do so.

? Comment (.doc or .pdf document) on the results: create a table of the results (by hand, not automatically), compare the numbers to the expected runtime performance (O(..?..)), and explain the result. Especially: think about what happens to the tree's topology (shape, balance) and how that influences the performance.

As you see, i leave the design as well as the details of the test to you. Please think WELL before you code. Also think about the expected results before you read them, and see if the actual computations match your expectations. Do NOT try to match your expectations to the results --- which is a non-scientific yet common way to misinterpret data.


THANK YOU

Explanation / Answer

In computer science, a binary search tree (BST) is a binary tree which has the following properties: Each node has a value. A total order is defined on these values. The left subtree of a node contains only values less than or equal to the node's value. The right subtree of a node contains only values greater than or equal to the node's value. The major advantage of binary search trees is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient. Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays. Following code shows how to implement a binary search tree in Java: // BinarySearchTree class // // CONSTRUCTION: with no initializer // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x // void removeMin( ) --> Remove minimum item // Comparable find( x ) --> Return item that matches x // Comparable findMin( ) --> Return smallest item // Comparable findMax( ) --> Return largest item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // ******************ERRORS******************************** // Exceptions are thrown by insert, remove, and removeMin if warranted /** * 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. * @param x the item to insert. * @throws DuplicateItemException if x is already present. */ public void insert( Comparable x ) { root = insert( x, root ); } /** * Remove from the tree.. * @param x the item to remove. * @throws ItemNotFoundException if x is not found. */ public void remove( Comparable x ) { root = remove( x, root ); } /** * Remove minimum item from the tree. * @throws ItemNotFoundException if tree is empty. */ public void removeMin( ) { root = removeMin( root ); } /** * Find the smallest item in the tree. * @return smallest item or null if empty. */ public Comparable findMin( ) { return elementAt( findMin( root ) ); } /** * Find the largest item in the tree. * @return the largest item or null if empty. */ public Comparable findMax( ) { return elementAt( findMax( root ) ); } /** * Find an item in the tree. * @param x the item to search for. * @return the matching item or null if not found. */ public Comparable find( Comparable x ) { return elementAt( find( 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; } /** * Internal method to get element field. * @param t the node. * @return the element field or null if t is null. */ private Comparable elementAt( BinaryNode t ) { return t == null ? null : t.element; } /** * Internal method to insert into a subtree. * @param x the item to insert. * @param t the node that roots the tree. * @return the new root. * @throws DuplicateItemException if x is already present. */ protected BinaryNode insert( Comparable x, BinaryNode t ) { if( t == null ) t = new BinaryNode( x ); else if( x.compareTo( t.element ) < 0 ) t.left = insert( x, t.left ); else if( x.compareTo( t.element ) > 0 ) t.right = insert( x, t.right ); else throw new DuplicateItemException( x.toString( ) ); // Duplicate return t; } /** * Internal method to remove from a subtree. * @param x the item to remove. * @param t the node that roots the tree. * @return the new root. * @throws ItemNotFoundException if x is not found. */ protected BinaryNode remove( Comparable x, BinaryNode t ) { if( t == null ) throw new ItemNotFoundException( x.toString( ) ); if( x.compareTo( t.element ) < 0 ) t.left = remove( x, t.left ); else if( x.compareTo( t.element ) > 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 = removeMin( t.right ); } else t = ( t.left != null ) ? t.left : t.right; return t; } /** * Internal method to remove minimum item from a subtree. * @param t the node that roots the tree. * @return the new root. * @throws ItemNotFoundException if x is not found. */ protected BinaryNode removeMin( BinaryNode t ) { if( t == null ) throw new ItemNotFoundException( ); else if( t.left != null ) { t.left = removeMin( t.left ); return t; } else return t.right; } /** * Internal method to find the smallest item in a subtree. * @param t the node that roots the tree. * @return node containing the smallest item. */ protected BinaryNode findMin( BinaryNode t ) { if( t != null ) while( t.left != null ) t = t.left; return t; } /** * Internal method to find the largest item in a subtree. * @param t the node that roots the tree. * @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 tree. * @return node containing the matched item. */ private BinaryNode find( Comparable x, BinaryNode t ) { while( t != null ) { if( x.compareTo( t.element ) < 0 ) t = t.left; else if( x.compareTo( t.element ) > 0 ) t = t.right; else return t; // Match } return null; // Not found } /** The tree root. */ protected 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( new Integer( i ) ); for( int i = 1; i

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.