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