Data Structures, Algorithms, & Applications in Java
Chapter 15, Exercise 13

First we must develop a method to randomly permute an array of elements. The random permutation can be obtained by considering the elements in the array from right to left. When the element in array position i is considered we generate a random number in the range 0 through i. Let the generated random number be j. The elements at i and j are swapped. The code is given below. 
public class Permute
{
   /** permute a[0:a.length-1] */
   public static void permute(Object [] a)
   {
      Random rand = new Random();
      for (int i = a.length - 1; i > 0; i--)
         // swap a[i] with a randomly selected element from a[0:i]
         MyMath.swap(a, i, Math.abs(rand.nextInt()) % (i + 1));
   }
}


The program to insert the elements into the binary search tree and then measure the tree height is given below. 
public class BinarySearchTreeHeight
{
   public static void main(String [] args)
   {
      // values for n, number of nodes in tree
      int [] size = {100, 500, 1000, 10000, 20000, 50000};
      int numOfTests = 6;
      int repeats = 10;
      int heightSum;
   
      for (int i = 0; i < numOfTests; i++)
      {// measure average height for size[i] elements
         heightSum = 0;
         Integer [] element = new Integer [size[i]];
         // generate size[i] elements to insert
         for (int j = 0; j < size[i]; j++)
            element[j] = new Integer(j);
           
         for (int r = 0; r < repeats; r++)
         {
            // randomly permute the elements
            Permute.permute(element);
         
            // create a binary search tree
            BinarySearchTree tree = new BinarySearchTree();
            // insert elements
            for (int j = 0; j < size[i]; j++)
               tree.put(element[j], element[j]);

            // add in its height
            heightSum += tree.height();
         }
      
         // output average tree height
         System.out.println("Number of nodes is " + size[i] +
              " Average height is " + heightSum / repeats);
      }
   }
}


The average heights output by this program for n = 100, 500, 1000, 10000, and 50000 are 13, 19, 21, 31, 33, and 37, respectively. The corresponding values of 2*ceil(log2(n+1)) are 14, 18, 20, 28, 30, and 32. The two sets of numbers are close.