Ternary Search Trees

Jon Bentley and Robert Sedgewick

feature article in Dr. Dobbs Journal April, 1998

Abstract

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.


Fast Algorithms for Sorting and Searching Strings

Jon Bentley and Robert Sedgewick

presented at Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
New Orleans, January, 1997

Abstract

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.com
Copyright (c) 1998, Robert Sedgewick and Jon Bentley