算法導(dǎo)論：字典樹(shù)
定義：Trie樹(shù)，即字典樹(shù)，又稱單詞查找樹(shù)或鍵樹(shù)。是一種用于快速檢索的多叉樹(shù)結(jié)構(gòu)。
Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來(lái)降低查詢時(shí)間的開(kāi)銷以達(dá)到提高效率的目的。
優(yōu)點(diǎn)：最大限度地減少無(wú)謂的字符串比較。
如果我們給定字符串集合為{b abc abd bcd abcd efg hii}，那么這個(gè)字符串的字典樹(shù)為：
字典樹(shù)
對(duì)于一顆字典樹(shù)來(lái)說(shuō)，應(yīng)該具有以下性質(zhì)：
性質(zhì)
第二條性質(zhì)中的到某個(gè)結(jié)點(diǎn)，就是指到紅色結(jié)點(diǎn)。
字典樹(shù)的構(gòu)建
字典樹(shù)的構(gòu)建
現(xiàn)在給出了，許多的字符串，我們從第一個(gè)字符串CAI開(kāi)始構(gòu)建。首先構(gòu)建根節(jié)點(diǎn)，其次構(gòu)建出CAI三個(gè)結(jié)點(diǎn)，
字典樹(shù)構(gòu)建
現(xiàn)在構(gòu)建字符串CAO因?yàn)镃A已經(jīng)存在，所以遍歷到A，發(fā)現(xiàn)O結(jié)點(diǎn)并不存在，生成O結(jié)點(diǎn)。
字典樹(shù)構(gòu)建
以此類推，最后生成的字典樹(shù)，如上圖所示。這個(gè)構(gòu)建過(guò)程，每一次都相當(dāng)于遍歷了一個(gè)字符串的長(zhǎng)度。
假如有n個(gè)字符串，那么它的時(shí)間復(fù)雜度就是，n乘上字符串的平均長(zhǎng)度。
字典樹(shù)的構(gòu)建
對(duì)于字典樹(shù)，在空間上的花費(fèi)為：
空間花費(fèi)：平均單詞長(zhǎng)度*結(jié)點(diǎn)長(zhǎng)度*單詞數(shù)
字典樹(shù)的查詢
構(gòu)建出字典樹(shù)
首先我們根據(jù)給出的單詞，構(gòu)建出了相應(yīng)的字典樹(shù)。
查詢
現(xiàn)在，我們要對(duì)inn這個(gè)單詞進(jìn)行查詢，當(dāng)然是從根節(jié)點(diǎn)先開(kāi)始。
查詢
按照結(jié)點(diǎn)進(jìn)行查詢，最后可以找到inn這個(gè)字符串。那么它的時(shí)間復(fù)雜度就是這個(gè)字符串的長(zhǎng)度O(len)。
字典樹(shù)的插入
插入
現(xiàn)在我們要插入新的字符串a(chǎn)tm，那應(yīng)該怎么做呢？
插入
在走到t結(jié)點(diǎn)時(shí)，發(fā)現(xiàn)沒(méi)有m結(jié)點(diǎn)，所以構(gòu)造出m結(jié)點(diǎn)，并變?yōu)榧t色。
字典樹(shù)的刪除
刪除
現(xiàn)在我們要?jiǎng)h除字典樹(shù)中的ant字符串，當(dāng)然是從根節(jié)點(diǎn)開(kāi)始去做一個(gè)查詢。
刪除
最后找到，結(jié)點(diǎn)t并且n結(jié)點(diǎn)也并沒(méi)有其他分支，所以在刪除時(shí)，會(huì)將n->t全部刪除。
刪除
最后結(jié)果如圖所示，時(shí)間復(fù)雜度也為O(len)。
字典樹(shù)的應(yīng)用
字典樹(shù)的應(yīng)用
