一、 序言
上一篇文章中，给出了 trie 树的一个实现。可以看到，trie 树有一个巨大的弊病，内存占用过大。
本文给出另一种数据结构来解决上述问题---- ternary search tree （三叉树）
二、数据结构定义
trie 树中每个节点包含了 26 个指针，但有很大一部分的指针是 null 指针，因此浪费了大量的资源。
一种改进措施就是，以一棵树来代替上述的指针数组。
节点定义如下：
一个节点代表了一个字母，左孩子的字母小于当前节点，右孩子的字母大于当前节点。
同时每个节点包含一个标记：指出当前节点是否是单词的结尾。
如下图：
这个图很容易理解错。我详细讲解以下。
首先，根节点是 a， 以 a 为开头的单词都在 中子树中;
左子树表示那些首字母 < a 的单词集合；
中子树表示那些首字母 = a 的单词集合；
右子树表示那些首字母 > a 的单词集合；
黄色表示单词的结尾；
下图中包含以下单词： ab abcd abba bcd
三、与 trie 树的比较
当建立一个 7000+ 的词典时，
1. trie 树共消耗了大约 22383 * 27 * 4 byte = 2.4 m
2. ternary tree 共消耗了 22468 * 14 byte = 0.31m
可以看出，在内存占用方面 ternary tree 较 trie 树有着巨大的优势。
四、代码