Trie又稱字典樹，是一種重要的數(shù)據(jù)結(jié)構(gòu)，是交流自動機(jī)的基礎(chǔ)。因此，讓我們簡要描述一下字典的數(shù)量，并列出對trie的操作。trie的形式如下圖所示：對于每個節(jié)點(diǎn)，從根遍歷到trie的過程是一個字。如果

Trie又稱字典樹，是一種重要的數(shù)據(jù)結(jié)構(gòu)，是交流自動機(jī)的基礎(chǔ)。因此，讓我們簡要描述一下字典的數(shù)量，并列出對trie的操作。trie的形式如下圖所示：對于每個節(jié)點(diǎn)，從根遍歷到trie的過程是一個字。如果節(jié)點(diǎn)標(biāo)記為紅色，則表示該詞存在，否則不存在。然后，對于一個單詞，我只需跟隨它的后跟到相應(yīng)的節(jié)點(diǎn)，然后查看該節(jié)點(diǎn)是否用紅色標(biāo)記，以知道它是否已出現(xiàn)。將此節(jié)點(diǎn)標(biāo)記為紅色相當(dāng)于插入單詞。這樣，我們就可以一起完成查詢和插入。所花的時間只是字長。在這個例子中，它是10。我們可以看到trie樹的每一層的節(jié)點(diǎn)數(shù)是26^I，這樣可以節(jié)省空間。我們使用動態(tài)鏈表或數(shù)組來模擬動態(tài)?？臻g成本不會超過字?jǐn)?shù)×字長。其基本性質(zhì)概括如下：1。根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外，每個節(jié)點(diǎn)僅包含一個字符。2從根節(jié)點(diǎn)到節(jié)點(diǎn)，路徑上的字符連接到節(jié)點(diǎn)的相應(yīng)字符串。三。每個節(jié)點(diǎn)的所有子節(jié)點(diǎn)都包含不同的字符。我們可以對動態(tài)存儲和靜態(tài)陣列進(jìn)行仿真，對于這兩種情況我們用poj2001和poj3630來解釋！