Trie 的實施

在閱讀本例之前，強烈建議你先閱讀 Trie 簡介 。

實現 Trie 的最簡單方法之一是使用連結串列。

節點：

節點將包括：

1. 結束標記的變數。
2. 指標陣列到下一個節點。

End-Mark 變數將簡單地表示它是否是終點。指標陣列將表示可以建立的所有可能的邊。對於英文字母，陣列的大小為 26，因為可以從單個節點建立最多 26 個邊。在開始時，指標陣列的每個值都將為 NULL，而結束標記變數將為 false。

Node:
Boolean Endmark
Node *next[26]
Node()
    endmark = false
    for i from 0 to 25
        next[i] := NULL
    endfor
endNode

next [] 陣列中的每個元素都指向另一個節點。 next [0] 指向節點共享 edge-a ， next [1] 指向節點共享 edge-b ，依此類推。我們已經定義了 Node 的建構函式來將 Endmark 初始化為 false，並將 NULL 放在 next [] 指標陣列的所有值中。

要建立 Trie ，首先我們需要例項化 root 。然後從根目錄開始，我們將建立其他節點來儲存資訊。

插入：

Procedure Insert(S, root):    // s is the string that needs to be inserted in our dictionary
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        curr -> next[id] = Node()
    curr := curr -> next[id]
endfor
curr -> endmark = true

我們在這裡與 az 合作。因此，要將它們的 ASCII 值轉換為 0-25 ，我們從它們中減去 a 的 ASCII 值。我們將檢查當前節點（curr）是否具有手頭角色的邊緣。如果是，我們使用該邊緣移動到下一個節點，如果不是，我們建立一個新節點。最後，我們將結束標記更改為 true。

搜尋：

Procedure Search(S, root)      // S is the string we are searching
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        Return false
    curr := curr -> id
Return curr -> endmark

該過程類似於插入。最後，我們返回結束標記。因此，如果結束是真的，那意味著單詞存在於字典中。如果它是假的，則字典中不存在該單詞。

這是我們的主要實施。現在我們可以在 trie 中插入任何單詞並搜尋它。

刪除：

有時我們需要擦除不再用於節省記憶體的單詞。為此，我們需要刪除未使用的單詞：

Procedure Delete(curr):       //curr represents the current node to be deleted
for i from 0 to 25
    if curr -> next[i] is not equal to NULL
        delete(curr -> next[i])
    delete(curr)               //free the memory the pointer is pointing to

此函式轉到 curr 的所有子節點，刪除它們然後刪除 curr 以釋放記憶體。如果我們呼叫 delete(root) ，它將刪除整個 Trie 。

Trie 也可以使用 Arrays 實現。