1 前缀树 Trie 概述
1.1 trie 概念介绍
前缀树 trie ，又称为字典树或者单词查找树，是一种广泛应用于本文词频统计场景的树状存储结构.
trie 这个名称源自于单词 retrieval. 根据词源学，trie 的发明者 Edward Fredkin 把它读作 /ˈtriː/ "tree"，而其他读者或使用方通常把它读作/ˈtraɪ/ "try".
trie 本身是一个多叉树结构，树中的每个节点存储一个字符，它与普通树状数据结构最大的差异在于，存储数据的 key 不存放于单个节点中，而是由从根节点 root 出发直到来到目标节点 target node 之间的沿途路径组成. 基于这样的构造方式，导致拥有相同前缀的字符串可以复用公共的父节点，直到在首次出现不同字符的位置才出现节点分叉，最终形成多叉树状结构.
下面我们通过一个案例加以说明：
如上图所示，我们描述一下插入 search、see、seat 三个单词的流程：
• 首先，trie 的根节点 root 内容为空. root 是所有节点的始祖、所有路径的起点
• 由于三个单词都有着公共的前缀 se，因此共享父节点 s、e
• 接下来，see 由于第三个字符为 e，与其他两个单词不同，以此 see 单独分叉出节点 e
• seat、search 由于第三个字符都为 a，因此共享节点 a
• seat、search 从第四个字符开始分叉，seat = sea + t；search = sea + r + c + h
• 至此，流程结束
回顾其结构特征，我们可以看出，trie 的优势是，当存储拥有公共前缀的内容时，可以在很大程度上节省空间提高节点利用率. 同时由于这种公共前缀的设计方式，也赋以了 trie 能够支持前缀频率统计以及前缀模糊匹配的功能.
1.2 trie 应用介绍
基于 trie 的特性，有一类很常用的应用场景就是搜索提示，比如当输入一个网址时，可以通过 trie 识别出用户可能的存在；当没有完全匹配的搜索结果时，也可以基于前缀返回最相似的可能.
除此之外，trie 存在另一个让我印象深刻的使用案例——geohash 算法.
简单来讲，geohash 是一种地址编码方式，通过将经纬度二维坐标通过递归二分的方式压缩成一个一维字符串，并能够在很大程度上保证拥有越长公共前缀的两个字符串之间的相对距离就越小.
由于 geohash 这种基于公共前缀圈定距离的实现方式，因此我们在存储基于 geohash 生成的大量位置信息时，通常会优先考虑使用 trie 树作为实现的数据结构.
上图是 geohash 实现思路的简单示例.
geohash 算法中还有很多技术思路与实现细节值得探讨，而且它还是我在自学编程过程中在首个实践项目中应用到的技术. 后续我会单开一篇，和大家展开聊聊 geohash 有关的话题，并且会对本文形成呼应，向大家详细介绍 geohash 中是如何对 trie 进行应用的.
2 前缀树 Trie 实现
2.1 leetcode 试题
针对于前缀树，大家不妨使用 leetcode 上的一道编程算法题来练练手：
题号：208
题名：实现Trie（前缀树）
链接：https://leetcode.cn/problems/implement-trie-prefix-tree/submissions/
2.2 核心类
下面，我们就进入实战环节，一起通过 Go 语言来从零到一实现一棵 trie 树：
首先针对于 trie 树中的节点 node，我们进行类型定义：
type trieNode struct {
nexts [26]*trieNode
passCnt int
end bool
}trieNode 中包含几个核心字段：
• passCnt：记录通过当前节点的单词数量. 即，以根节点到当前节点所形成字符串作为前缀的单词数量
• end：标识是否存在单词以当前节点为结尾. 即，存在以从根节点到当前节点所形成字符串作为内容的单词
• nexts：子节点列表. trie树通过这一项，形成了父子节点一对多的映射关系，最终形成了多叉树的拓扑结构.
在本轮实现中，我们将单词的字符限定为 a-z 组成的 26 个小写字母. 在每个节点对应的 nexts 切片中，nexts[0] 表示下一个节点对应字符为 'a'，nexts[1] 对应为 'b'，以此类推，直到 nexts[25] 对应为 'z'.
下面是关于前缀树 trie 的定义，定义很简单，trie 中需要持有一个根节点 root 即可. 其中 root 是所有 trieNode 节点的始祖，其本身对应的字符为空.
type Trie struct {
root *trieNode
}
func NewTrie() *Trie {
return &Trie{
root: &trieNode{},
}
}
2.3 查询流程
下面我们展示一下，检索一个单词，判断其是否存在于 trie 树的处理流程：
func (t *Trie) Search(word string) bool {
// 查找目标节点，使得从根节点开始抵达目标节点沿路字符形成的字符串恰好等于 word
node := t.search(word)
return node != nil && node.end
}• Trie.Search 方法通过嵌套调用 Trie.search 方法，查找满足从根节点开始抵达该节点所形成字符串恰好等于检索单词 word 的目标节点
• 如果节点存在，并且节点的 end 标识为 true，代表 word 存在
下面是 Trie.search 方法的源码：
func (t *Trie) search(target string) *trieNode {
// 移动指针从根节点出发
move := t.root
// 依次遍历 target 中的每个字符
for _, ch := range target {
// 倘若 nexts 中不存在对应于这个字符的节点，说明该单词没插入过，返回 nil
if move.nexts[ch-'a'] == nil {
return nil
}
// 指针向着子节点移动
move = move.nexts[ch-'a']
}
// 来到末尾，说明已经完全匹配好单词，直接返回这个节点
// 需要注意，找到目标节点不一定代表单词存在，因为该节点的 end 标识未必为 true
// 比如我们之前往 trie 中插入了 apple 这个单词，但是查找 app 这个单词时，预期的返回结果应该是不存在，此时就需要使用到 end 标识 进行区分
return move
}在 Trie.search 方法中：
• 移动指针 move 从 trie 的根节点 root 出发
• 依次遍历 word 中的字符，查看 move 的子节点列表 nexts 中否存在对应于该字符的子节点
• 如果对应子节点不存在，说明目标不存在
• 如果子节点存在，则将 move 指向该子节点，开始下一轮遍历
• 当遍历结束时，此时 move 对应的一定是 target 末尾的字符，直接返回 move 指向的节点
• 在外层方法 Trie.Search 中，会通过该节点的 end 标识，判断是否确实存在单词以该节点作为结尾
2.4 前缀匹配流程
下面是查看 trie 中是否存在单词以指定 prefix 作为前缀的处理流程.
在 StartWith 方法中，通过复用 trie.search 方法，返回全路径对应为 prefix 的节点. 根据该节点存在与否，可以判断出是否存在单词使用到了 prefix 前缀.
StartWith 流程与 Search 流程的区别在于，StartWith 无需对节点的 end 标识进行判断，因为此时我们的查询条件更宽松，只需要作前缀匹配，而非精确匹配.
func (t *Trie) StartsWith(prefix string) bool {
return t.search(prefix) != nil
}
2.5 前缀统计流程
下面展示一下 trie 树的另一种用法：给定一个 prefix，要求统计出以 prefix 作为前缀的单词数量.
func (t *Trie) PassCnt(prefix string) int {
node := t.search(prefix)
if node == nil {
return 0
}
return node.passCnt
}关于这一点，我们保证在后续处理单词插入的 Insert 流程以及单词删除的 Erase 流程中，对每个节点维护好一个 passCnt 计数器，用于记录通过该节点的单词数量.
因此在此处的 PassCnt 流程中，我们只需要根据 prefix 找到对应节点，然后直接返回节点对应的 passCnt 值即可.
2.6 插入流程
下面展示了将一个单词 word 插入到 trie 树对应流程的实现源码：
func (t *Trie) Insert(word string) {
if t.Search(word) {
return
}
move := t.root
for _, ch := range word {
if move.nexts[ch-'a'] == nil {
move.nexts[ch-'a'] = &trieNode{}
}
move.nexts[ch-'a'].passCnt++
move = move.nexts[ch-'a']
}
move.end = true
}流程核心步骤包括：
• 插入新单词前，先检查一下，单词是否已存在了. 如果是的话，则直接结束流程，无需重复插入
• 移动指针 move 以根节点 root 作为起点
• 依次遍历 word 的每个字符，每轮判断当前节点的子节点列表 nexts 中，对应于字符的子节点是否已存在了
• 如果不存在，则首先创建出这个子节点
• 由于存在新单词的插入，我们需要对这个子节点的 passCnt 计数器累加 1
• 移动 move 指针，使其指向字符对应的子节点，并开启下一轮循环
• 重复上述流程，直到遍历结束，此时 move 所在位置一定对应的是单词结尾的字符. 我们需要把 move 指向节点的 end 标识置为 true，代表存在单词以此节点作为结尾
2.7 删除流程
最后展示一下，从前缀树 trie 中删除某个单词对应的实现源码：
func (t *Trie) Erase(word string) bool {
if !t.Search(word) {
return false
}
move := t.root
for _, ch := range word {
move.nexts[ch-'a'].passCnt--
if move.nexts[ch-'a'].passCnt == 0 {
move.nexts[ch-'a'] = nil
return true
}
move = move.nexts[ch-'a']
}
move.end = false
return true
}上述流程的核心步骤包括：
• 前置判断一下，拟删除单词 word 是否存在. 如果不存在，就提前结束流程，不用白费力气
• 移动指针 move 以根节点 root
• 依次遍历 word 中的每个字符，每次从当前节点子节点列表 nexts 中找到对应于字符的子节点
• 把该子节点的 passCnt 减 1
• 倘若发现子节点的 passCnt 被减为 0，则直接舍弃这个子节点，结束流程
• 倘若遍历来到单词末尾位置，则需要把对应节点的 end 标识置为 false
到这里为止，我就把前缀树 trie 的实现流程全部介绍完了. 针对上述源码实现，如果其中存在纰漏或者大家有优雅的实现方式，欢迎提出探讨.
3 压缩前缀树 Radix Tree 概述
3.1 radix tree 概念介绍
从第 3 章开始，我们一起聊一个前缀树 trie 的升级版本——压缩前缀树/基数树 radix tree.
radix tree 是一种更加节省空间的 trie. 首先，radix tree 传承了来自 trie 的基本设定，本身也是基于多叉树的数据结构实现，在多叉树中，每个节点对应一段相对路径，最终从根节点到某个节点之间沿路途径的所有相对路径拼接在一起后形成的绝对路径，即为该节点对应的标识键 key.
radix tree 相比于 trie 而言，核心的区别主要体现在一个处理规则上：
• 倘若某个父节点有且仅有一个子节点，并且不存在单词以这个父节点作为结尾，则此时 radix tree 会将这个父节点与子节点进行合并，并把父、子节点的相对路径组装在一起生成一段复合的相对路径，以此作为这个“新生节点”的相对路径
基于这样的规则，我们不难看出，radix tree 相较于 trie 而言，存在的优势就是能够起到节省空间的效果.
radix tree 的一类常用场景是路由匹配模块. 以插入如下图所示的几条 path 为例，最终生成的压缩前缀树 radix tree 如下：
可以看到，其中如 "ba"、"se"、"nana"、"arch" "/v" "app" "le" 几个部分都基于 radix tree 的新规则实现了父子节点之间的压缩合并.
在上述例子中，arch 没有和唯一的子节点 /v 进行压缩合并，原因是在于存在于 arch 作为结尾的单词——/search，因此 arch 需要单独拆出一个节点.
3.2 radix tree 应用介绍
关于 radix tree 的应用，其中一个很经典的一个工程案例就是 gin 框架中针对路由模块的设计实现.
gin 框架是 Golang 中最流行的 web 框架之一，开源地址：https://github.com/gin-gonic/gin
在 gin 框架中，使用 radix tree 作为路由树的数据结构，建立了请求路径 pattern 和路径处理函数链 handlers 之间的映射关系. 之所以选用 radix tree 而非 hashmap，其原因在于：
• 在路由匹配时，除了需要根据请求路径进行精确匹配之外，还有着模糊匹配的诉求. 比如请求路径末尾 '/' 符号的增减、通配符 '*' 的使用等，这种非单点匹配的操作不适合使用 map，而 radix tree 则是能够满足诉求
• 各路由长度相比于数量而言更加有限，使用 radix tree 实现的话可以有更好的性能表现
radix tree 具体实现是比较具有难度的，主要在于随着单词的插入和删除，需要对 radix tree 结构进行动态调整，涉及到对父子节点的合并和拆分. 本文第 4 章内容中对 radix tree 的源码还原就是借鉴了 gin 框架中的实现，更多有关于 gin 的内容，大家可以阅读我之前发表的文章——解析 Gin 框架底层原理.
4 压缩前缀树 Radix Tree 实现
第 4 章开始，我们展示一下 radix tree 的具体实现源码.
4.1 核心类
首先，我们需要针对 radix tree 中节点的类型进行定义：
type radixNode struct {
// 当前节点的相对路径
path string
// 完整路径
fullPath string
// 每个 indice 字符对应一个孩子节点的 path 首字母
indices string
// 后继节点
children []*radixNode
// 是否有路径以当前节点为终点
end bool
// 记录有多少路径途径当前节点
passCnt int
}在节点 radixNode 中，包含核心字段：
• path：当前节点对应的相对路径
• fullPath：当前节点对应的前缀路径. 指的是从根节点 root 出发到达当前节点的过程中，把沿路节点相对路径拼接在一起得到的结果
• indices：后继子节点首字母组合成的字典
• children：后继子节点列表，子节点的顺序需要和 indices 中保持一致
• end：是否存在单词以当前节点作为结尾
• passCnt：存在多少当前，以当前节点作为前缀
下面是有关整棵压缩前缀树 radix tree 的定义，其中内置了一个根节点 root，并通过子节点列表 children 形成整个树状的拓扑结构.
需要注意，radix tree 和 trie 所不同的是，root 节点是能够存储实际的相对路径 path 的.
type Radix struct {
root *radixNode
}
func NewRadix() *Radix {
return &Radix{
root: &radixNode{},
}
}
4.2 插入流程
往 radix tree 中插入一个单词 word 的流程图如上图所示，具体的源码如下所示，在源码中已经针对关键步骤给出了相应的注释：
func (r *Radix) Insert(word string) {
// 不重复插入
if r.Search(word) {
return
}
r.root.insert(word)
}
func (rn *radixNode) insert(word string) {
fullWord := word
// 如果当前节点为 root，此之前没有注册过子节点，则直接插入并返回
if rn.path == "" && len(rn.children) == 0 {
rn.insertWord(word, word)
return
}
walk:
for {
// 获取到 word 和当前节点 path 的公共前缀长度
i := commonPrefixLen(word, rn.path)
// 只要公共前缀大于 0，则一定经过当前节点，需要累加 passCnt
if i > 0{
rn.passCnt++
}
// 公共前缀小于当前节点的相对路径，需要对节点进行分解
if i < len(rn.path) {
// 需要进行节点切割
child := radixNode{
// 进行相对路径切分
path: rn.path[i:],
// 继承完整路径
fullPath: rn.fullPath,
// 当前节点的后继节点进行委托
children: rn.children,
indices: rn.indices,
end: rn.end,
// 传承给孩子节点时，需要把之前累加上的 passCnt 计数扣除
passCnt: rn.passCnt-1,
}
// 续接上孩子节点
rn.indices = string(rn.path[i])
rn.children = []*radixNode{&child}
// 调整原节点的 full path
rn.fullPath = rn.fullPath[:len(rn.fullPath)-(len(rn.path)-i)]
// 调整原节点的 path
rn.path = rn.path[:i]
// 原节点是新拆分出来的，目前不可能有单词以该节点结尾
rn.end = false
}
// 公共前缀小于插入 word 的长度
if i < len(word) {
// 对 word 扣除公共前缀部分
word = word[i:]
// 获取 word 剩余部分的首字母
c := word[0]
for i := 0; i < len(rn.indices); i++ {
// 如果与后继节点还有公共前缀，则将 rn 指向子节点，然后递归执行流程
if rn.indices[i] == c {
rn = rn.children[i]
continue walk
}
}
// 到了这里，意味着 word 剩余部分与后继节点没有公共前缀了
// 此时直接构造新的节点进行插入
rn.indices += string(c)
child := radixNode{}
child.insertWord(word, fullWord)
rn.children = append(rn.children, &child)
return
}
// 倘若公共前缀恰好是 path，需要将 end 置为 true
rn.end = true
return
}
}
// 求取两个单词的公共前缀
func commonPrefixLen(wordA, wordB string) int {
var move int
for move < len(wordA) && move < len(wordB) && wordA[move] == wordB[move] {
move++
}
return move
}
// 传入相对路径和完整路径，补充一个新生成的节点信息
func (rn *radixNode) insertWord(path, fullPath string) {
rn.path, rn.fullPath = path, fullPath
rn.passCnt = 1
rn.end = true
}下面我们对插入流程的核心步骤进行总结：
• 首先，检查一下 word 是否已存在，如果存在，则终止流程，无需重复操作
• 以 radix tree 的根节点 root 作为起点，调用 radixNode.insert 方法，执行插入流程
• 如果此前 radix tree 中从未插入过任何单词，则直接将首个单词插入到 root 当中
• 开启 for 循环，根据节点的相对路径 path 与插入 word 之间的关系进，进行分类处理：
• 求出 path 与 word 的公共前缀长度 i
• 如果公共前缀 i 大于 0，说明 word 必然经过当前节点，需要对 passCnt 计数器加 1
• 如果公共前缀 i 小于 path 长度，则要将当前节点拆分为公共前缀部分 + 后继剩余部分两个节点
• 如果公共前缀长度小于 word 长度，则需要继续检查，word 和后继节点是否还有公共前缀，如果有的话，则递归对后继节点执行相同流程
• 当保证 word 和后继节点不再有公共前缀，则直接将 word 包装成一个新的节点，插入到当前节点的子节点列表 children 当中
4.3 查询流程
查询一个单词 word 是否存在于 radix tree 对应的流程如上图所示，具体代码如下所示：
// 查看一个单词在 radix 当中是否存在
func (r *Radix) Search(word string) bool {
node := r.root.search(word)
return node != nil && node.fullPath == word && node.end
}
func (rn *radixNode) search(word string) *radixNode {
walk:
for {
prefix := rn.path
// word 长于 path
if len(word) > len(prefix) {
// 没匹配上，直接返回 nil
if word[:len(prefix)] != prefix {
return nil
}
// word 扣除公共前缀后的剩余部分
word = word[len(prefix):]
c := word[0]
for i := 0; i < len(rn.indices); i++ {
// 后继节点还有公共前缀，继续匹配
if c == rn.indices[i] {
rn = rn.children[i]
continue walk
}
}
// word 还有剩余部分，但是 prefix 不存在后继节点和 word 剩余部分有公共前缀了
// 必然不存在
return nil
}
// 和当前节点精准匹配上了
if word == prefix {
return rn
}
// 走到这里意味着 len(word) <= len(prefix) && word != prefix
return rn
}
}上述源码的核心步骤总结如下：
• 调用 radix tree 根节点 root 对应的 search 方法，开启查询流程
• 倘若 word 内容刚好和节点 path 相等，则返回节点，并在上层通过节点的 end 标识，判断是否存在单词以当前节点结尾
• 倘若 word 以节点 path 作为前缀，则查看后继节点是否还与 path 存在公共前缀，如果是的话，将节点指针指向后继节点，递归开启后续流程
• 除此之外，都说明 word 不存于 radix tree 中，直接终止流程
4.4 前缀匹配流程
func (r *Radix) StartWith(prefix string) bool {
node := r.root.search(prefix)
return node != nil && strings.HasPrefix(node.fullPath, prefix)
}在前缀匹配流程中：
• 我们通过调用根节点 root 的 search 方法，检索出可能包含 prefix 为前缀的节点 node
• 如果对应节点存在，并且其全路径 fullPath 确实以 prefix 为前缀，则前缀匹配成功
4.5 前缀统计流程
func (r *Radix) PassCnt(prefix string) int {
node := r.root.search(prefix)
if node == nil || !strings.HasPrefix(node.fullPath, prefix) {
return 0
}
return node.passCnt
}在前缀统计流程中：
• 我们通过调用根节点 root 的 search 方法，检索出可能包含以 prefix 为前缀的节点 node
• 如果对应节点存在并且其全路径 fullPath 确实以 prefix 为前缀，则返回该节点 passCnt 计数器的值
4.6 删除流程
最后我们来到从 radix tree 中删除一个单词的流程当中，具体实现如下：
// 删除调一个字典
func (r *Radix) Erase(word string) bool {
if !r.Search(word) {
return false
}
// root 直接精准命中了
if r.root.fullPath == word {
// 如果一个孩子都没有
if len(r.root.indices) == 0 {
r.root.path = ""
r.root.fullPath = ""
r.root.end = false
r.root.passCnt = 0
return true
}
// 如果只有一个孩子
if len(r.root.indices) == 1 {
r.root.children[0].path = r.root.path + r.root.children[0].path
r.root = r.root.children[0]
return true
}
// 如果有多个孩子
for i := 0; i < len(r.root.indices); i++ {
r.root.children[i].path = r.root.path + r.root.children[0].path
}
newRoot := radixNode{
indices: r.root.indices,
children: r.root.children,
passCnt: r.root.passCnt - 1,
}
r.root = &newRoot
return true
}
// 确定 word 存在的情况下
move := r.root
// root 单独作为一个分支处理
// 其他情况下，需要对孩子进行处理
walk:
for {
move.passCnt--
prefix := move.path
word = word[len(prefix):]
c := word[0]
for i := 0; i < len(move.indices); i++ {
if move.indices[i] != c {
continue
}
// 精准命中但是他仍有后继节点
if move.children[i].path == word && move.children[i].passCnt > 1 {
move.children[i].end = false
move.children[i].passCnt--
return true
}
// 找到对应的 child 了
// 如果说后继节点的 passCnt = 1，直接干掉
if move.children[i].passCnt > 1 {
move = move.children[i]
continue walk
}
move.children = append(move.children[:i], move.children[i+1:]...)
move.indices = move.indices[:i] + move.indices[i+1:]
// 如果干掉一个孩子后，发现只有一个孩子了，并且自身 end 为 false 则需要进行合并
if !move.end && len(move.indices) == 1 {
// 合并自己与唯一的孩子
move.path += move.children[0].path
move.fullPath = move.children[0].fullPath
move.end = move.children[0].end
move.indices = move.children[0].indices
move.children = move.children[0].children
}
return true
}
}
}上述代码核心步骤为：
• 通过 Search 方法判断拟删除单词是否存在，如果不存在直接 return
• 如果 word 刚好和根节点 root 的 path 相等，需要对根节点的所有子节点进行路径 path 调整，同时需要对 radix tree 的根节点指针进行调整
• 从根节点 root 出发进行匹配，沿路将途径到的子节点的 passCnt 计数器数值减 1
• 倘若途中发现某个子节点的 passCnt 被减为 0，则直接删除该节点. 删除某个子节点后，需要判断，当前节点是否满足和下一个子节点进行压缩合并的条件，如果的是话，需要执行合并操作
5 总结
本期和大家一起探讨了一个在实现思路上另辟蹊径的树状 kv 存储结构——前缀树 trie.
以 trie 为基础，我们进一步探讨了它的升级版本——压缩前缀树/基数树 radix tree.
在通过实现原理结合实践源码进行内容介绍的同时，本文还简单介绍了应用到这两种数据结构的工程案例，包括使用 trie 作为经纬度哈希编码存储结构的 geohash 算法，以及使用 radix tree 作为路由存储结构的 gin 框架.
