I was using such a definition:

"Given any binary search tree with n nodes, where each node has associated with it a probability (the sum of all probabilities of all nodes in a tree is equal to 1), then the number of nodes expected to be examined for any given key is equal to the mean of the sum of the product of the probability of each node and it's level in the tree (root = 1)." In other words:

  n   (pk)(lk)
  Ó   --------
k = 1    n

Where pk is the probability for the kth node and lk is the depth of the kth node in the tree, where the root is 1.
     

And in most of the example trees I tried, the balanced one resulted in the lowest number (the result only makes sense relative to the values of other trees).

[edited by - Zipster on October 31, 2002 6:22:20 PM]