BSTTest.java

import java.util.*;

public class BSTTest
{
      private static final boolean debug = true;
      
      public static void main(String[] args)
      {
         Random rnd = new Random();
         BinarySearchTree bst = new BinarySearchTree();
         int numItems;
         
         if (args.length > 0)
         {
            numItems = Integer.parseInt(args[0]);
         }
         else
         {
            numItems = 1000;
         }
         
         // My code (just the next line)
         Integer[] numbers = new Integer[numItems];

         for (int i = 0; i < numItems; i++)
         {
            Integer newNumber = new Integer(rnd.nextInt());

            try
            {
               bst.insert(newNumber);
            }
            catch (DuplicateItemException e) { }

            // My code (just the next line)
            numbers[i] = newNumber;
         }
         
         log("BST height: " + bst.height());
         
         // My code (from here on)
         Arrays.sort(numbers);

         final int SEARCH_COUNT = 100000;

         Date treeSearchStartTime = new Date();

         for (int currentSearchNumber = 0;
              currentSearchNumber < SEARCH_COUNT;
              currentSearchNumber ++)
         {
            bst.find(new Integer(rnd.nextInt()));
         }

         Date treeSearchEndTime = new Date();

         System.out.println("Searching the tree for " +
                            SEARCH_COUNT + " random ints took " +
                            (treeSearchEndTime.getTime() -
                             treeSearchStartTime.getTime()) +
                            " milliseconds");

         Date arraySearchStartTime = new Date();

         for (int currentSearchNumber = 0;
              currentSearchNumber < SEARCH_COUNT;
              currentSearchNumber ++)
         {
            Arrays.binarySearch(numbers, new Integer(rnd.nextInt()));
         }

         Date arraySearchEndTime = new Date();

         System.out.println("Searching the array for " +
                            SEARCH_COUNT + " random ints took " +
                            (arraySearchEndTime.getTime() -
                             arraySearchStartTime.getTime()) +
                            " milliseconds");
      }
      
      private static void log(String str)
      {
         if (debug)
         {
            System.out.println(str);
         }
      }
}

1,000
Min: 19
Avg: 23
Max: 26

10,000
Min: 27
Avg: 30
Max: 35

100,000
Min: 37
Avg: 39
Max: 43

1,000,000
Min: 46
Avg: 49
Max: 51

Searching the tree for 100000 random ints took 215 milliseconds
Searching the array for 100000 random ints took 167 milliseconds