A C++ package that implements ternary search tree, which combines the time efficiency of digital tries with the space efficiency of binary search trees. It it is reported comparable with hashing table in most cases, and substantially faster than hashing for unsuccessful searches.
C++
Switch branches/tags
Nothing to show
Clone or download
Latest commit 124c509 Apr 10, 2015

README.md

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:

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.