1. 什么是trie樹
1.Trie樹 （特例結(jié)構(gòu)樹）
Trie樹劫拗，又稱單詞查找樹辜妓、字典樹，是一種樹形結(jié)構(gòu)碌宴，是一種哈希樹的變種杀狡，是一種用于快速檢索的多叉樹結(jié)構(gòu)。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串）贰镣，所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)呜象。它的優(yōu)點(diǎn)是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高碑隆。
Trie的核心思想是空間換時(shí)間恭陡。利用字符串的公共前綴來降低查詢時(shí)間的開銷以達(dá)到提高效率的目的。
Trie樹也有它的缺點(diǎn),Trie樹的內(nèi)存消耗非常大.當(dāng)然,或許用左兒子右兄弟的方法建樹的話,可能會(huì)好點(diǎn).
- 三個(gè)基本特性：
1）根節(jié)點(diǎn)不包含字符上煤，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符休玩。
2）從根節(jié)點(diǎn)到某一節(jié)點(diǎn)劫狠，路徑上經(jīng)過的字符連接起來拴疤，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串《琅ⅲ
3）每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同呐矾。
3 .例子
和二叉查找樹不同，在trie樹中懦砂，每個(gè)結(jié)點(diǎn)上并非存儲(chǔ)一個(gè)元素蜒犯。
trie樹把要查找的關(guān)鍵詞看作一個(gè)字符序列。并根據(jù)構(gòu)成關(guān)鍵詞字符的先后順序構(gòu)造用于檢索的樹結(jié)構(gòu)荞膘。
在trie樹上進(jìn)行檢索類似于查閱英語詞典罚随。
一棵m度的trie樹或者為空，或者由m棵m度的trie樹構(gòu)成衫画。
例如毫炉，電子英文詞典，為了方便用戶快速檢索英語單詞削罩，可以建立一棵trie樹瞄勾。例如詞典由下面的單詞成：a、b弥激、c进陡、aa、ab微服、ac趾疚、ba、ca、aba糙麦、abc辛孵、baa、bab赡磅、bac魄缚、cab、abba焚廊、baba冶匹、caba、abaca咆瘟、caaba
再舉一個(gè)例子嚼隘。給出一組單詞，inn, int, at, age, adv, ant, 我們可以得到下面的Trie：
可以看出：
每條邊對(duì)應(yīng)一個(gè)字母袒餐。
每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一項(xiàng)前綴飞蛹。葉節(jié)點(diǎn)對(duì)應(yīng)最長前綴，即單詞本身匿乃。
單詞inn與單詞int有共同的前綴“in”, 因此他們共享左邊的一條分支桩皿，root->i->in豌汇。同理幢炸，ate, age, adv, 和ant共享前綴"a"，所以他們共享從根節(jié)點(diǎn)到節(jié)點(diǎn)"a"的邊拒贱。
查詢操縱非常簡單宛徊。比如要查找int，順著路徑i -> in -> int就找到了逻澳。
2. trie樹的實(shí)現(xiàn)
1．插入過程
對(duì)于一個(gè)單詞闸天，從根開始，沿著單詞的各個(gè)字母所對(duì)應(yīng)的樹中的節(jié)點(diǎn)分支向下走斜做，直到單詞遍歷完苞氮，將最后的節(jié)點(diǎn)標(biāo)記為紅色，表示該單詞已插入trie樹瓤逼。
- 查找過程
其方法為：
(1) 從根結(jié)點(diǎn)開始一次搜索笼吟；
(2) 取得要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對(duì)應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索霸旗；
(3) 在相應(yīng)的子樹上贷帮，取得要查找關(guān)鍵詞的第二個(gè)字母,并進(jìn)一步選擇對(duì)應(yīng)的子樹進(jìn)行檢索。
(4) 迭代過程……
(5) 在某個(gè)結(jié)點(diǎn)處诱告，關(guān)鍵詞的所有字母已被取出撵枢，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找。其他操作類似處理.
即從根開始按照單詞的字母順序向下遍歷trie樹锄禽，一旦發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)標(biāo)記不存在或者單詞遍歷完成而最后的節(jié)點(diǎn)未標(biāo)記為紅色潜必，則表示該單詞不存在，若最后的節(jié)點(diǎn)標(biāo)記為紅色沃但，表示該單詞存在刮便。如下圖中：trie樹中存在的就是abc、d绽慈、da恨旱、dda四個(gè)單詞。在實(shí)際的問題中可以將標(biāo)記顏色的標(biāo)志位改為數(shù)量count等其他符合題目要求的變量坝疼。
- 查找分析
在trie樹中查找一個(gè)關(guān)鍵字的時(shí)間和樹中包含的結(jié)點(diǎn)數(shù)無關(guān)搜贤，而取決于組成關(guān)鍵字的字符數(shù)。而二叉查找樹的查找時(shí)間和樹中的結(jié)點(diǎn)數(shù)有關(guān)O(log2n)钝凶。
如果要查找的關(guān)鍵字可以分解成字符序列且不是很長仪芒，利用trie樹查找速度優(yōu)于二叉查找樹。如：
若關(guān)鍵字長度最大是5耕陷，則利用trie樹掂名，利用5次比較可以從26^5＝11881376個(gè)可能的關(guān)鍵字中檢索出指定的關(guān)鍵字。而利用二叉查找樹至少要進(jìn)行次比較哟沫。
3. trie樹的應(yīng)用：
字符串檢索饺蔑，詞頻統(tǒng)計(jì)，搜索引擎的熱門查詢
事先將已知的一些字符串（字典）的有關(guān)信息保存到trie樹里嗜诀，查找另外一些未知字符串是否出現(xiàn)過或者出現(xiàn)頻率猾警。
舉例：
1）有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞隆敢，詞的大小不超過16字節(jié)发皿，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞拂蝎。
2）給出N 個(gè)單詞組成的熟詞表穴墅，以及一篇全用小寫英文書寫的文章，請(qǐng)你按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞温自。
3）給出一個(gè)詞典玄货，其中的單詞為不良單詞。單詞均為小寫字母捣作。再給出一段文本誉结，文本的每一行也由小寫字母構(gòu)成。判斷文本中是否含有任何不良單詞券躁。例如惩坑，若rob是不良單詞掉盅，那么文本problem含有不良單詞。
4）1000萬字符串以舒，其中有些是重復(fù)的趾痘，需要把重復(fù)的全部去掉，保留沒有重復(fù)的字符串
5）尋找熱門查詢：搜索引擎會(huì)通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來蔓钟，每個(gè)查詢串的長度為1-255字節(jié)永票。假設(shè)目前有一千萬個(gè)記錄，這些查詢串的重復(fù)讀比較高滥沫，雖然總數(shù)是1千萬侣集，但是如果去除重復(fù)和，不超過3百萬個(gè)兰绣。一個(gè)查詢串的重復(fù)度越高世分，說明查詢它的用戶越多，也就越熱門缀辩。請(qǐng)你統(tǒng)計(jì)最熱門的10個(gè)查詢串臭埋，要求使用的內(nèi)存不能超過1G。-
字符串最長公共前綴
Trie樹利用多個(gè)字符串的公共前綴來節(jié)省存儲(chǔ)空間臀玄，反之瓢阴，當(dāng)我們把大量字符串存儲(chǔ)到一棵trie樹上時(shí)，我們可以快速得到某些字符串的公共前綴健无。舉例：- 給出N 個(gè)小寫英文字母串荣恐，以及Q 個(gè)詢問，即詢問某兩個(gè)串的最長公共前綴的長度是多少睬涧？
解決方案：
- 給出N 個(gè)小寫英文字母串荣恐，以及Q 個(gè)詢問，即詢問某兩個(gè)串的最長公共前綴的長度是多少睬涧？
首先對(duì)所有的串建立其對(duì)應(yīng)的字母樹募胃。此時(shí)發(fā)現(xiàn)，對(duì)于兩個(gè)串的最長公共前綴的長度即它們所在結(jié)點(diǎn)的公共祖先個(gè)數(shù)畦浓，于是，問題就轉(zhuǎn)化為了離線 （Offline）的最近公共祖先（Least Common Ancestor检疫，簡稱LCA）問題
而最近公共祖先問題同樣是一個(gè)經(jīng)典問題讶请，可以用下面幾種方法：
利用并查集（Disjoint Set），可以采用采用經(jīng)典的Tarjan 算法屎媳；
求出字母樹的歐拉序列（Euler Sequence ）后夺溢，就可以轉(zhuǎn)為經(jīng)典的最小值查詢（Range Minimum Query，簡稱RMQ）問題了烛谊；
-
排序
Trie樹是一棵多叉樹风响，只要先序遍歷整棵樹，輸出相應(yīng)的字符串便是按字典序排序的結(jié)果丹禀。舉例： 給你N 個(gè)互不相同的僅由一個(gè)單詞構(gòu)成的英文名状勤，讓你將它們按字典序從小到大排序輸出鞋怀。
作為其他數(shù)據(jù)結(jié)構(gòu)和算法的輔助結(jié)構(gòu)
如后綴樹，AC自動(dòng)機(jī)等持搜。
————————————————
本文是轉(zhuǎn)載密似，原文鏈接：https://blog.csdn.net/hguisu/article/details/8131559
