Optimizing binary trees grown with a sorting algorithm
- 1 February 1972
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 15 (2) , 88-93
- https://doi.org/10.1145/361254.361259
Abstract
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.Keywords
This publication has 4 references indexed in Scilit:
- A balanced tree storage and retrieval algorithmPublished by Association for Computing Machinery (ACM) ,1971
- Information retrievalPublished by Association for Computing Machinery (ACM) ,1965
- An empirical study of minimal storage sortingCommunications of the ACM, 1963
- Algorithm 63: partitionCommunications of the ACM, 1961