Optimizing Binary Trees Grown With a Sorting Algorithm

Items can be retrieved from binary trees grown
with a form of the Algorithm Quicksort in an 
average time proportional to log n, where n is the number
of items in the tree.  The binary trees grown 
by this algorithm sometimes have some branches longer
than others; therefore, it is possible to reduce 
the average retrieval time by restructuring the tree to
make the branches as uniform in length as possible. 
 An algorithm to do this is presented.  The use of this
algorithm is discussed, and it is compared with 
another which restructures the tree after each new item is added.

CACM February, 1972

Martin, W. A.
Ness, D. N.

retrieving information from binary trees, global
and local optimization, sorting, recursion

3.74 5.31

CA720203 JB January 31, 1978  4:30 PM

1175	4	2388
1919	4	2388
1919	4	2388
1969	4	2388
1997	4	2388
2191	4	2388
2191	4	2388
2388	4	2388
2388	4	2388
2679	4	2388
2783	4	2388
2784	4	2388
3054	4	2388
3054	4	2388
3121	4	2388
3121	4	2388
864	4	2388
308	5	2388
309	5	2388
2388	5	2388
2388	5	2388
2388	5	2388
2455	5	2388
2493	5	2388
2889	5	2388
2968	5	2388
2138	6	2388
2278	6	2388
2388	6	2388
2388	6	2388
2388	6	2388
2388	6	2388
2455	6	2388
2455	6	2388