On the Probability Distribution of the Values of Binary Trees

An integral equation is derived for the generating
function for binary tree values, the values 
reflecting sorting effort. The analysis does not assume
uniformly distributed branching ratios, and 
therefore is applicable to a family of sorting algorithms
discussed by Hoare, Singleton, and van Emden. 
 The solution to the integral equation indicates that
using more advanced algorithms in the family makes 
only minor reductions in the expected sorting effort,
but substantially reduces the variance in sorting 
effort.  Statistical tests of the values of several
thousand trees containing up to 10,000 points have 
given first, second, and third moments of the value distribution
function in satisfactory agreement with 
the moments computed from the generating function.  The
empirical tests, as well as the analytical results, 
are in agreement with previously published results for the
first moment in the cases of uniform and nonuniform 
distribution of branching ratio, and for the second moment
in the case of uniform distribution of branching 
ratio.

CACM February, 1971

Hurwitz Jr., H.

binary trees, sorting, statistical analysis

4.40 5.18 5.5

CA710205 JB February 8, 1978  9:09 AM

1175	4	2216
1919	4	2216
1997	4	2216
2017	4	2216
2041	4	2216
2216	4	2216
2216	4	2216
2216	4	2216
2216	4	2216
2679	4	2216
2679	4	2216
3054	4	2216
3054	4	2216
3054	4	2216
1919	5	2216
1969	5	2216
1997	5	2216
2216	5	2216
2216	5	2216
2216	5	2216
864	5	2216