Trie樹(shù)就是字符樹(shù)，其核心思想就是空間換時(shí)間。

舉個(gè)簡(jiǎn)單的例子。

給你100000個(gè)長(zhǎng)度不超過(guò)10的單詞。對(duì)于每一個(gè)單詞，我們要判斷他出沒(méi)出現(xiàn)過(guò)，如果出現(xiàn)了，第一次出現(xiàn)第幾個(gè)位置。

這題當(dāng)然可以用hash來(lái)，但是我要介紹的是trie樹(shù)。在某些方面它的用途更大。比如說(shuō)對(duì)于某一個(gè)單詞，我要詢問(wèn)它的前綴是否出現(xiàn)過(guò)。這樣hash就不好搞了，而用trie還是很簡(jiǎn)單。

現(xiàn)在回到例子中，如果我們用最傻的方法，對(duì)于每一個(gè)單詞，我們都要去查找它前面的單詞中是否有它。那么這個(gè)算法的復(fù)雜度就是O(n^2)。顯然對(duì)于100000的范圍難以接受。現(xiàn)在我們換個(gè)思路想。假設(shè)我要查詢的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類開(kāi)頭的我顯然不必考慮。而只要找以a開(kāi)頭的中是否存在abcd就可以了。同樣的，在以a開(kāi)頭中的單詞中，我們只要考慮以b作為第二個(gè)字母的……這樣一個(gè)樹(shù)的模型就漸漸清晰了……

假設(shè)有b，abc，abd，bcd，abcd，efg，hii這6個(gè)單詞，我們構(gòu)建的樹(shù)就是這樣的。

對(duì)于每一個(gè)節(jié)點(diǎn)，從根遍歷到他的過(guò)程就是一個(gè)單詞，如果這個(gè)節(jié)點(diǎn)被標(biāo)記為紅色，就表示這個(gè)單詞存在，否則不存在。

那么，對(duì)于一個(gè)單詞，我只要順著他從跟走到對(duì)應(yīng)的節(jié)點(diǎn)，再看這個(gè)節(jié)點(diǎn)是否被標(biāo)記為紅色就可以知道它是否出現(xiàn)過(guò)了。把這個(gè)節(jié)點(diǎn)標(biāo)記為紅色，就相當(dāng)于插入了這個(gè)單詞。

這樣一來(lái)我們?cè)儐?wèn)和插入可以一起完成，所用時(shí)間僅僅為單詞長(zhǎng)度，在這一個(gè)樣例，便是10。

我們可以看到，trie樹(shù)每一層的節(jié)點(diǎn)數(shù)是26^i級(jí)別的。所以為了節(jié)省空間。我們用動(dòng)態(tài)鏈表，或者用數(shù)組來(lái)模擬動(dòng)態(tài)。空間的花費(fèi)，不會(huì)超過(guò)單詞數(shù)×單詞長(zhǎng)度。