Trie tree: 前缀树, 又称字典树, 是N叉树的特殊形式.

基本概念#

Trie树是用来解决一组字符串集合中快速查找某个字符串的问题.

• 数据结构

[image:999FE3AB-7090-4EAF-81D8-0037257B7FCE-894-00000DFC95BA724D/280fbc0bfdef8380fcb632af39e84b32.jpg]

* 根节点: 不包含任何信息
* 每个节点: 树中的每个节点表示一个字符串中的一个字符, 从根节点到红色节点的一条路径表示一个字符串.

注意: 红色节点并不都是叶子节点

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起

如何表示一个前缀树#

• 数组

用数组存储每一层的节点, 例如我们要存储的都是a~z的字母, 那么就可以声明一个长度为26的数组. 当我们要找’c’时, 就可以通过'c'-'a'的值来访问.

优势: 访问便捷 略势: 空间浪费

• Map

用Map存储每一层的节点. key为这一层的字符, value为字符的子节点.

优势: 节省空间 略势: 比数组访问慢

补充. Trie树中, 每个节点除了存储字符外, 当需要判断当前节点是否为一个完整单词时, 需要别的字段来辅助, 比如每个节点添加一个 bool 变量, 用来判断是否为一个完整单词.

注意: 完整单词的节点不一定是叶子节点. 比如: hi, hight, 中的i, 不是叶子节点, 但是hi是一个完整的单词.

实现一个前缀树#

力扣: 208. 实现一个Trie树

package trie

type Trie struct {
	isWorld bool
	child map[byte]*Trie
}


/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{child: make(map[byte]*Trie)}
}


/** Inserts a word into the trie. */
func (this *Trie) Insert(word string)  {
	node := this
	child := this.child
	for _, char := range word {
		if c, exists := child[byte(char)]; exists {
			node = c
			child = c.child
		} else {
			node = &Trie{
				isWorld: false,
				child:   make(map[byte]*Trie),
			}
			child[byte(char)] = node
			child = node.child
		}
	}
	node.isWorld = true
}


/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
	isWorld := false
	child := this.child
	for _, char := range word {
		if c, exists := child[byte(char)]; !exists {
			isWorld = false
			break
		} else {
			isWorld = c.isWorld
			child = c.child
		}
	}
	return isWorld
}


/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
	child := this.child
	for _, char := range prefix {
		if c, exists := child[byte(char)]; !exists {
			return false
		} else {
			child = c.child
		}
	}
	return true
}

实际应用#

前缀树广泛应用于 存储 字符串和 检索 关键字，特别是和 前缀 相关的关键字。

1. 自动补全: 如搜索框的自动补全
2. 拼写检查

677. 键值映射 648. 单词替换 642. 设计搜索自动补全系统 211. 添加与搜索单词 - 数据结构设计

实际应用二#

1. 加速深度优先搜索 有时，我们会用前缀树来加速深度优先搜索。特别是当我们使用深度优先搜索解决文字游戏类问题的时候。
2. 存储其他数据类型
3. 还有一些其他应用，例如 IP 路由（最长前缀匹配）

421. 数组中两个数的最大异或值 212. 单词搜索 II 425. 单词方块 336. 回文对

参考#

• 力扣（LeetCode）

#01 Blog/算法相关#