Tree Structures for Optimal Searching

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.

REFERENCES

• 1: Edward H. Sussenguth, Jr., Use of tree structures for processing files, Communications of the ACM, v.6 n.5, p.272-279, May 1963 [doi>10.1145/366552.366600]
• 2: KARP, R.M. Minimum redundancy coding for the discrete, noiseless channel. IRE Trans. IT-7 (1961), 27-35.
• 3: GOMORY, R. E. An algorithm for integer solutions to linear programs. In Recent Advances in Mathematical Programming, Graves, R. L., and Wolfe, P. (Eds.), McGraw- Hill, New York, 1963, pp. 269-302. (First made known in 1958.)
• 4: Yale N. Patt, Variable length tree structures having minimum average search time, Communications of the ACM, v.12 n.2, p.72-76, Feb. 1969 [doi>10.1145/362848.362853]
• 5: S. R. Arora , W. T. Dent, Randomized binary search technique, Communications of the ACM, v.12 n.2, p.77-80, Feb. 1969 [doi>10.1145/362848.362856]
• 6: Larry E. Stanfel, A comment on optimal tree structures, Communications of the ACM, v.12 n.10, p.582, Oct. 1969 [doi>10.1145/363235.363265]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Design, Measurement, Performance, Theory