A RUN-TIME ESTIMATE OF THE AVERAGE HEIGHT OF A BINARY SEARCH TREE

This lab focuses on the height of a binary search tree, and provides run-time support for the claim, in Chapter 9, that the average height of a binary search tree is logarithmic in n, the size of the tree.

The height of a BinarySearchTree

In Chapter 10, a claim is made that the average height of a binary search tree is logarithmic in n. In this lab, you will provide some support for that claim through a run-time experiment.

To start, recall the definition of a height function from Chapter 9:

for a binary tree t, we define the height of t, written height (t) as:

if t is empty, height (t) = -1;
otherwise, height (t) = 1 + max (height (leftTree (t)), height (rightTree (t))

This definition uses functional notation, not object-oriented notation. Here is the specification of a height method in the BinarySearchTree class:

/**
 * The height of this BinarySearchTree has been calculated and returned.
 *
 * @return an int containing the height of the BinarySearchTree.
 **/
public int height();