All searches are divided into three parts: string searches using ternary trees

ABSTRACT

This paper considers the problem of searching for strings in a dictionary or symbol table. It presents a data structure which can be used for this purpose---the Ternary Tree. It considers the theoretical properties of this structure, compared with other possible structures for the same purpose. It presents an implementation of this structure in APL, including code to do a variety of operations on it.

REFERENCES

• 1: BENTLEY, J.L. and SEDGEWICK, R., "Ternary Search Trees", Dr. Dobb's Journal (pp 20-27) Vol. 23 No. 4 (April 1998)
• 2: Robert Sedgewick, Algorithms in C, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 3: Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: Julien Clément , Philippe Flajolet , Brigitte Vallée, The analysis of hybrid trie structures, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.531-539, January 25-27, 1998, San Francisco, California, United States
• 5: Harry A. Clampett, Jr., Randomized binary searching with tree structures, Communications of the ACM, v.7 n.3, p.163-165, March 1964 [doi>10.1145/363958.363987]
• 6: http://www.cs.princeton.edu/rs/strings/ Website maintained by Robert Sedgewick including example C code for TSTs.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  E. Data

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Design, Languages

Keywords:
data structure, dictionary search, radix search, search algorithms, search tree, symbol table, ternary tree