Tree Structures for Optimal Searching
- 1 July 1970
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 17 (3) , 508-517
- https://doi.org/10.1145/321592.321601
Abstract
It is shown that, owing to certain restrictions placed upon the set of admissible structures, some previous solutions have not characterized trees in which expected search time is minimized. The more general problem is shown to be a special case of a coding problem, which was previously formulated and solved as a linear integer programming problem, and in the special case of equally probable key requests is found to be solvable almost by inspection. Some remarks are given regarding the possibility of realizing a shorter computational procedure than would be expected from an integer programming algorithm, along with a comparison of results from the present method with those of the previous.Keywords
This publication has 4 references indexed in Scilit:
- A comment on optimal tree structuresCommunications of the ACM, 1969
- Randomized binary search techniqueCommunications of the ACM, 1969
- Variable length tree structures having minimum average search timeCommunications of the ACM, 1969
- Use of tree structures for processing filesCommunications of the ACM, 1963