update (2016-04-05):
Ternary Search Tree (improved)的实现有误,将稍后更正。
There is always a topic that how to store a set of strings. Throughout the years, many kinds of data structure had been proposed and applied, for instance, hash tables, binary search tree, digital search tree, ternary search tree and so on and so forth.
如何存储一组字符串总是一个经久不衰的话题。在这些年间,有许多种不同的数据结构不断被提出和应用,例如哈希表、二分搜索树、数字查找树、三元搜索树等等。
Let's begin with ternary search tree which is proposed by Jon and Robert at Pricenton[1]. There is one more pointer in the node compared with binary search tree, and it's the exactly minor change that not only makes it combine the time efficiency of digital tries with the space efficiency of binary search trees, but also provides more features like prefix search and fuzz search.
让我们从三元搜索树开始,它是由Jon和Robert在Pricenton[1]提出的。和二分搜索树相比起来,它的每个节点中多了一个指针,也正是这么一个小小的改动,不仅使它结合了数字查找树的时间效率和二分搜索树的空间效率,还使得它提供了诸如前缀搜索和模糊搜索这样的特性。
But can we make it more efficient in time with a tolerable space increment? We need to analyse the algorithm and the data structure of ternary search tree.
但是我们能在可容忍的空间使用增加上,进一步提高它的时间效率吗?我们需要分析三元搜素树的算法与结构。
Continue reading Quinary Search Tree →