Ternary Search Trees

Download source code: Click here to download

This package includes files of TernarySearchTree class.

Ternary search tree stores keys in sorted order, which can be used as a symbol table.

Searching operation is lightning fast, it is reported comparable with hashing table in most cases, and substantially faster than hashing for unsuccessful searches.

Ternary search tree gracefully grows and shrinks, unlike hash table which usually use an array and need to be rebuilt after large size changes.

Advance operations such as traversal to get sorted item list, partial matching and near-neighbor search are supported natively.

Ternary search tree is initially proposed by Jon Bentley and Bob Sedgewick on 1997.

see references:

Fast Algorithms for Sorting and Searching Strings: http://www.cs.princeton.edu/~rs/strings/paper.pdf

Ternary Search Trees: http://www.ddj.com/documents/s=921/ddj9804a/9804a.htm

The folder of the dictionary file in main.cpp file need to be changed according to your setting.

If you found any bug, please kindly send email to me at jerryy@gmail. Comments or suggestions are very welcomed.


Jan 16, 2006. Zheyuan Yu.

Initial creation of ternary search tree class

SourceForge.net Logo