Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結(jié)構(gòu)，如英文字母的字典樹是一個26叉樹，數(shù)字的字典樹是一個10叉樹。
三叉搜索樹是一種特殊的Trie樹的數(shù)據(jù)結(jié)構(gòu)，它是數(shù)字搜索樹和二叉搜索樹的混合體。它既有數(shù)字搜索樹效率優(yōu)點，又有二叉搜索樹空間優(yōu)點。
在接下來的博文中，我們將介紹Trie樹和三叉搜索樹的定義，實現(xiàn)和優(yōu)缺點。
Trie樹的定義
Trie樹與二叉搜索樹不同，鍵不是直接保存在節(jié)點中，而是由節(jié)點在樹中的位置決定。一個節(jié)點的所有子孫都有相同的前綴（prefix），也就是這個節(jié)點對應(yīng)的字符串，而根節(jié)點對應(yīng)空字符串。一般情況下，不是所有的節(jié)點都有對應(yīng)的值，只有葉子節(jié)點和部分內(nèi)部節(jié)點所對應(yīng)的鍵才有相關(guān)的值。
Trie樹可以利用字符串的公共前綴來節(jié)約存儲空間，如下圖所示，該Trie樹用11個節(jié)點保存了8個字符串tea，ted，ten，to，A，i，in，inn。
圖1Trie樹
我們注意到Trie樹中，字符串tea，ted和ten的相同的前綴（prefix）為“te”，如果我們要存儲的字符串大部分都具有相同的前綴（prefix），那么該Trie樹結(jié)構(gòu)可以節(jié)省大量內(nèi)存空間，因為Trie樹中每個單詞都是通過character by character方法進行存儲，所以具有相同前綴單詞是共享前綴節(jié)點的。
當(dāng)然，如果Trie樹中存在大量字符串，并且這些字符串基本上沒有公共前綴，那么相應(yīng)的Trie樹將非常消耗內(nèi)存空間，Trie的缺點是空指針耗費內(nèi)存空間。
Trie樹的基本性質(zhì)可以歸納為：
（1）根節(jié)點不包含字符，除根節(jié)點外的每個節(jié)點只包含一個字符。
（2）從根節(jié)點到某一個節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。
（3）每個節(jié)點的所有子節(jié)點包含的字符串不相同。
喜歡 
頂
難過
囧
圍觀
無聊
