Trie又稱字典樹，是重要的數據結構，也是AC自動機的基礎，因此在這裏簡單的說下什麽是字典數，並且列舉Trie上的操作。Trie的形式如下圖所示：?
對於每壹個節點，從根遍歷到他的過程就是壹個單詞，如果這個節點被標記為紅色，就表示這個單詞存在，否則不存在。
那麽，對於壹個單詞，我只要順著他從跟走到對應的節點，再看這個節點是否被標記為紅色就可以知道它是否出現過了。把這個節點標記為紅色，就相當於插入了這個單詞。
這樣壹來我們詢問和插入可以壹起完成，所用時間僅僅為單詞長度，在這壹個樣例，便是10。
我們可以看到，trie樹每壹層的節點數是26^i級別的。所以為了節省空間。我們用動態鏈表，或者用數組來模擬動態。空間的花費，不會超過單詞數×單詞長度。
基本性質可以歸納為：
1.?根節點不包含字符，除根節點外每壹個節點都只包含壹個字符。?
2.?從根節點到某壹節點，路徑上經過的字符連接起來，為該節點對應的字符串。?
3.?每個節點的所有子節點包含的字符都不相同。
我們可以動態存儲和靜態數組模擬，對於這兩種情況我們分別用POJ2001和POJ3630進行解釋！