????字典樹，又稱為 Trie樹，單詞查找樹，是一種樹形結(jié)構(gòu)，也是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。

????它的優(yōu)點(diǎn)是，利用字符串的公共前綴來(lái)減少查詢時(shí)間，最大限度地減少無(wú)謂地字符串比較，查詢效率比哈希樹高。

????字典樹的 3 個(gè)基本性質(zhì)：

????1） 根結(jié)點(diǎn)不包含字符，除根結(jié)點(diǎn)以外每一個(gè)結(jié)點(diǎn)都只包含一個(gè)字符；

????2）從根結(jié)點(diǎn)到某一結(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串；

????3）每個(gè)結(jié)點(diǎn)的所有子結(jié)點(diǎn)包含的字符都不相同。

???? 例如，圖中 bee 是一個(gè)單詞， beer也是一個(gè)單詞，此時(shí)可以在每個(gè)單詞結(jié)束位置加一個(gè) end[ ] 標(biāo)記，就直到從根到這里有一個(gè)單詞。

????字典的基本操作： 查找，插入和刪除，極少出現(xiàn)刪除操作。

????字典樹的應(yīng)用：

（1）字典樹的創(chuàng)建

算法代碼：

（2）字典樹的查找

? ? 算法代碼：

性能分析：