go语言数据结构之前缀树Trie

前缀树Trie

前缀树Trie是一种树形数据结构，被用于快速查找内存中的字符串数据。它非常适合存储大量的字符串，并且能够非常快速的查找以一个指定的字符串前缀开头的全部字符串。

相关术语

在学习前缀树Trie之前，需要掌握一下相关术语：

• 根节点：Trie树的根节点，代表空字符串。
• 边：连接两个节点的线，代表一个字符。
• 节点：表示一个字符串，可能是某个字符串的结尾，也可能是某个字符串的前缀。
• 叶子节点：表示某个字符串的结尾。
• 结尾标志：表示某个字符串的结束。在Trie树中，可以通过一个节点的is_end属性来标记此节点是否为某个字符串的结尾。

建立Trie

我们来看一下如何建立一棵Trie树。我们以一个字符串数组为例：

words := []string{"hello", "world", "what", "why", "when", "how"}

Trie树的根节点为一个空字符串的节点，接下来将words中的字符串放入Trie树中。

对于每个字符串，将其每个字符按序放入Trie树中，如果该字符对应的节点不存在，则创建该节点。当该字符串放完时，将该字符串的结尾标志设置为true。

具体实现可以参考下面的代码示例：

type Trie struct {
    children [26]*Trie
    isEnd    bool
}

func Constructor() Trie {
    return Trie{}
}

func (this *Trie) Insert(word string) {
    node := this
    for _, c := range word {
        if node.children[c-'a'] == nil {
            node.children[c-'a'] = &Trie{}
        }
        node = node.children[c-'a']
    }
    node.isEnd = true
}

查找Trie

Trie树的查找操作也非常简单。对于每个字符，如果对应的节点不存在，则表示Trie树中不存在该字符串，可以直接返回false。一旦该字符串的所有字符都被遍历完毕，则查找成功。

对于前缀查找操作，做法也很类似：只要找到前缀的最后一个字符对应的节点，然后遍历该节点的所有子节点即可。

可以通过以下代码来实现查找操作：

func (this *Trie) Search(word string) bool {
    node := this
    for _, c := range word {
        if node.children[c-'a'] == nil {
            return false
        }
        node = node.children[c-'a']
    }
    return node.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
    node := this
    for _, c := range prefix {
        if node.children[c-'a'] == nil {
            return false
        }
        node = node.children[c-'a']
    }
    return true
}

示例

下面是一个Trie树的示例：

              root
            /   |   \
           h    w    s
           |    |    |
           e    o    e
          /|\   |    |
         l r i  r    e
         | |     |   |
         l d     l   c
                  |   |
                  d   t

上图是一个Trie树的示例，包含了以下字符串：

hello, world, what, why, when, how

例如，要查询字符串"hello"是否在Trie树中，只需从根节点开始按字符串中的字母序列找到对应节点，如果最后到达叶子节点并且该节点的isEnd属性为true，则表示该字符串在Trie树中。而对于询问Trie树中是否存在以"h"开头的字符串，只需沿着"h"对应的边向下遍历即可。

总结

前缀树Trie是一种高效的数据结构，可以支持快速的查找和前缀查找操作。在实际应用中，它被广泛应用于路由表、单词矫正、字典查询等领域。