A comment on optimal tree structures

ABSTRACT

In Y.N. Patt's paper “Variable Length Tree Structures Having Minimum Average Search Time” [Comm. ACM 12 (Feb. 1969)], the tree structures obtained are not actually optimal with respect to the two-dimensional chaining devised by Sussenguth in his 1963 paper. This note points out that the result can be described as “optimal” only under the constraint—which Patt implicity assumes—that no key be allowed to prefix another.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

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

General Terms:
Languages, Management

Keywords:
double chaining, file searching, information retrieval, tree structures