feature article in Dr. Dobbs Journal April, 1998
When you have to store a set of strings, what data structure do you use? Jon and Bob suggest one place you can start is with ternary search trees, which combine the time efficiency of digital tries with the space efficiency of binary search trees.
presented at Eighth Annual ACM-SIAM Symposium on Discrete Algorithms New Orleans, January, 1997
We present theoretical algorithms for sorting and searching multidimensional data and practical C implementations for the application where keys are character strings. The sorting algorithm, an amalgam of Quicksort and radix sort, is competitive with the best known C sort codes. The searching algorithm, an amalgam of tries and binary search trees, is faster than hashing and other commonly used search methods. The basic ideas behind the algorithms date back at least to the 1960s, but their practical utility has been overlooked. Analytic results and extensions to more difficult string processing problems are also included.
Comments, questions, suggestions:
mail rs@cs.princeton.edu mail jlb@research.bell-labs.comCopyright (c) 1998, Robert Sedgewick and Jon Bentley