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 实现。