概念

字典树也称前缀树，用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串，是一种高效地存储和查找字符串集合的数据结构。

代码模版

数据结构

1
2
3
4
5
6
7
8
type Trie struct {
    children [26]*Trie //孩子结点表示当前字符
    isEnd bool //当前字符是否为结尾
}

func Constructor() Trie {
    return Trie{}
}

插入

1
2
3
4
5
6
7
8
9
10
11
func (t *Trie) Insert(word string)  {
    node := t
    for _, ch := range word {
        ch -= 'a'
        if node.children[ch] == nil {
            node.children[ch] = &Trie{}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

查找前缀

1
2
3
4
5
6
7
8
9
10
11
func (t *Trie) SearchPrefix(prefix string) *Trie {
    node := t
    for _, ch := range prefix {
        ch -= 'a'
        if node.children[ch] == nil{
            return nil
        }
        node = node.children[ch]
    }
    return node
}

精确准找

1
2
3
4
func (t *Trie) Search(word string) bool {
    node := t.SearchPrefix(word)
    return node != nil && node.isEnd 
}

习题

LeetCode 208 实现前缀树
AcWing 835 Trie字符串统计

扩展

压缩字典（Radix)树

Radix树将只有一个子节点的中间节点将被压缩，使之具有更加合理的内存使用和查询的效率，同时可以在节点中增加权值字段，拥有的子串越多，就越靠近树的左侧（for遍历时更早匹配到）。

在Gin框架中动态路由的实现运用了此数据结构。