Finding an optimal tree searching strategy in linear time

ABSTRACT

We address the extension of the binary search technique from sorted arrays and totally ordered sets to trees and tree-like partially ordered sets. As in the sorted array case, the goal is to minimize the number of queries required to find a target element in the worst case. However, while the optimal strategy for searching an array is straightforward (always query the middle element), the optimal strategy for searching a tree is dependent on the tree's structure and is harder to compute. We present an O(n)-time algorithm that finds the optimal strategy for binary searching a tree, improving the previous best O(n³)-time algorithm. The significant improvement is due to a novel approach for computing subproblems, as well as a method for reusing parts of already computed subproblems, and a linear-time transformation from a solution in the form of an edge-weighed tree into a solution in the form of a decision tree.

REFERENCES

• 1: Stephen Alstrup , Jens Peter Secher , Maz Spork, Optimal on-line decremental connectivity in trees, Information Processing Letters, v.64 n.4, p.161-164, Nov. 28, 1997 [doi>10.1016/S0020-0190(97)00170-1]
• 2: Yosi Ben-Asher , Eitan Farchi , Ilan Newman, Optimal Search in Trees, SIAM Journal on Computing, v.28 n.6, p.2090-2102, Dec. 1999 [doi>10.1137/S009753979731858X]
• 3: R. Carmo , J. Donadelli , Y. Kohayakawa , E. Laber, Searching in random partially ordered sets, Theoretical Computer Science, v.321 n.1, p.41-57, June 16, 2004 [doi>10.1016/j.tcs.2003.06.001]
• 4: Moses Charikar , Ronald Fagin , Venkatesan Guruswami , Jon Kleinberg , Prabhakar Raghavan , Amit Sahai, Query strategies for priced information, Journal of Computer and System Sciences, v.64 n.4, p.785-819, June 2002 [doi>10.1006/jcss.2002.1828]
• 5: C. Daskalakis, R. M. Karp, E. Mossel, S. Riesen-feld, and E. Verbin. Sorting and selection in posets. arXiv:0707.1532, 2007.
• 6: E. Demaine. Private communication, 2007.
• 7: U. Faigle , G. Turán, Sorting and recognition problems for ordered sets, SIAM Journal on Computing, v.17 n.1, p.100-113, Feb. 1988 [doi>10.1137/0217007]
• 8: David E. Ferguson, Fibonaccian searching, Communications of the ACM, v.3 n.12, p.648, Dec. 1960 [doi>10.1145/367487.367496]
• 9: William J. Knight, Search in an ordered array having variable probe cost, SIAM Journal on Computing, v.17 n.6, p.1203-1214, Dec. 1988 [doi>10.1137/0217076]
• 10: D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, second edition, 1998.
• 11: E. Laber and L. T. Nogueira. Fast searching in trees. Electronic Notes in Discrete Mathematics, 7:1--4, 2001.
• 12: N. Linial and M. Saks. Every poset has a central element. Journal of combinatorial theory, A 40(2):195--210, 1985.
• 13: N. Linial and M. Saks. Searching ordered structures. Journal of algorithms, 6(1):86--103, 1985.
• 14: G. Navarro, R. Baeza-Yates, E. Barbosa, N. Ziviani, and W. Cunto. Binary searching with non-uniform costs and its application to text retrieval. Algorithmica, 27(2):145--169, 2000.
• 15: Krzysztof Onak , Pawel Parys, Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.379-388, October 21-24, 2006 [doi>10.1109/FOCS.2006.32]
• 16: W. W. Peterson. Addressing for random-access storage. IBM Journal of Research and Development, 1(2):130--146, 1957.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching; Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Theory