一、 序言
上一篇文章中，給出了 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 樹有着巨大的優勢。
四、代碼