热门标签
热门文章
- 1从结构上浅谈FPGA实现逻辑的原理_lut和ram的转换关系
- 2Java 2024年面试总结（持续更新）_java2024
- 3SQL Server数据库文件过大而无法直接导出解决方案_sqlserver查询数据量大需要导出
- 4比特率和波特率的计算公式及举例说明_1秒钟传输10个比特 请问频率是多少
- 5如何将idea的代码提交到git_idea怎么提交代码到git
- 6软件设计之JavaScript(2)
- 7暗网排名Top10的搜索引擎_notevil搜索引擎
- 8一款拥有AI功能的数据库管理工具_有没有哪个ai支持数据库
- 9Stable Diffusion Controlnet 1.0基础用法_stalb diffousion controlnet v1.0
- 10AI人工智能在2020年的7个发展趋势_aiscratch手机自动化功能的市场趋势
当前位置: article > 正文
数据结构之树从入门到如土(三)----字典树 前缀树(TrieTree) Go 实现_tire tree
作者：小桥流水78 | 2024-08-17 22:54:35
赞
踩
tire tree
字典树的简介
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。
Tree 树 是利用空间复杂度作为代价换区时间复杂度的应用,查找复杂度 为 o(Len),空间复杂度 是比较大的。
下面这个图是一个由 RA RC RZ RAC RAD RACE 等等组成 红色的节点 被标记成 了一个单词的结尾。
字典树的应用场景
- 求最近公共祖先，需要利用tire树作为数据结构
- 排序：前序遍历tire树，即可以得到一个按字母顺序的排序表
- 字符串检索：在搜索引擎中会用的(搜索时会弹出可能的单词结果)，主要是已知一个字符串集合，对这个集合进行预处理生成一个tire树，以后就维护这个tire树即可。
Tire用于统计：
题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。
解法 ：从第一个单词开始构造Tire树，Tire树包含两字段，字符与位置，对于非结尾字符，其位置标0，结尾字符，标注在100000个单词词表中的位置。对词表建造Tire树，对每个词检索到词尾，若词尾的数字字段>0,表示单词已经在之前出现过，否则建立结尾字符标志，下次出现即可得知其首次出现位置，便利词表即可依次计算出每个单词首次出现位置复杂度为O（N×L）L为最长单词长度，N为词表大小
Tire用于排序
题目：对10000个英文名按字典顺序排序
解法：建造Tire树，先序便利即可得到结果。
基本数据结构
type trieNode struct {
isWord bool//是否单词结尾
next map[byte][]*trieNode //子节点
}
type Trie struct{
size int //大小
root *trieNode //根节点
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
首先 我们定义了 trie 节点 的基本数据结构,每个节点记录了 所有子节点的指针。 Trie 结构 定义了 大小 和 根节点。
首先 我们构造了一颗 Trie树,初始化Root节点。
//初始化 Trie树
func NewTrie() *Trie{
node := trieNode{
isWord: false,
next: make(map[byte][]*trieNode,0),
}
a := Trie{
size: 0,
root: &node,
}
return &a
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
结构很简单 就像 一个链表一样 只不过 有点区别 就是 每个节点 都有多个 子节点。
增删改查 我们先实现 增加:
这里面使用了非递归的方式,首先得到 root 下面的 所有节点,然后 遍历 节点
找不到 就新建 找到了 把 当前节点指针cur 改成 下一个节点指针,然后 如果是插入到最后一个字符了 ,就把 isWord 修改成True
//往 节点内 添加内容 func(trie *Trie) Insert(content string){ node := trieNode{ isWord: false, next: make(map[byte]*trieNode,0), } if content == ""{ panic("error!") } if trie.root == nil{ trie.root = &node } rootnode := trie.root.next var cur *trieNode for i,v := range []byte(content){ var tmpnode *trieNode //如果cur为 nil if cur == nil{ if rootnode[v] == nil{ tmpnode = &trieNode{ isWord: false, next: make(map[byte]*trieNode,0), } //如果是字符串 结尾 if len(content) -1 == i{ tmpnode.isWord = true } cur = tmpnode rootnode[v] = cur }else{ cur = rootnode[v] } //如果 cur 已经被初始化 }else { if cur.next[v] == nil{ tmpnode = &trieNode{ isWord: false, next: make(map[byte]*trieNode,0), } //如果是字符串 结尾 if len(content) -1 == i{ tmpnode.isWord = true } cur.next[v] = tmpnode cur = tmpnode }else{ //如果是字符串 结尾 if len(content) -1 == i{ cur.isWord = true } cur = cur.next[v] } } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
有了 添加指定字符串,接下来我们再来写一个查找是否包含的方法:
让我们整理下思路,要查找 是否包含指定字符串
先定义一个 指针 记录当前节点
var cur *node
然后遍历 要查找的字符串
for i,key range := str
第一次 当前节点 就直接从根节点拿,
if cur == nil
cur == root.next
否则的话 从 子节点列表 取得 然后 根新为当前节点
else
cur = cur.next[key]
如果 cur 为 空 的话 表明 没找到
然后 如果 找到 字符串最后一个节点,但是字符串没有被 设置为 单词 就认为 没有找到。
上面的步骤其实很简单,比起插入来说。当然 如果用递归 可以跟简介一些。但其实 也差不多。下面给出代码。
func (trie *Trie) Contains(content string) bool{ if trie.root == nil{ panic("error nil") } var cur *trieNode //当前节点指针 for i,v := range []byte(content){ if cur == nil{ //第一次 从root的next子节点获取 cur = trie.root.next[v] }else{ //当前节点 的next子节点里获取 cur = cur.next[v] } //如果 没有 获取到 认为 没有 if cur == nil{ return false } //如果已经 到达了最后一个节点 但是这个节点没有被标记成 单词 if len(content) -1 == i && cur.isWord == false{ return false } } //如果 上面条件都不满足 则认为 找到了 return true }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
下面再来写个 遍历所有 Trie树里内容吧
这里我们用 递归 比较方便。 其实就是递归搜索,一直搜索 遍历完 所有 节点 然后 把每个节点记录的 字符 传递到下一个节点,如果是 单词就打印。
func deepSearchx(root *trieNode,deep int,res []byte) { if root.isWord{ //如果 是一个单词 打印 fmt.Println(string(res)) } for k,v := range root.next{ //搜索深度 if deep <= 0{ return } tmp := make([]byte,0,0) tmp = append(tmp,res...) tmp =append(tmp,k) //不停递归传递 切片 deepSearchx(v, deep -1, tmp) } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
下面 是 我测试了下 代码:
下面顺便实现 下 删除的代码吧
有了上面的代码 要实现这个 是不是跟 玩一样。。。。
分解步骤 只需要两步:
第一步 找到 那个单词的根节点
第二部 判断 是不是单词,如果不是 我们不需要修改返回false 如果 是 单词 修改返回true
这里 我们 参考 ,Contains的代码做一点小修改就好了。
其实 如果 简单的话加上一行删除就好了。但是 如果删除了树 是不是 得回收原来的空间 。所以 我们需要在添加一个方法 递归 把 没用的节点删除了 这个 可以参考Search 的代码 .
这里用递归的思路
思路是这样的,如果 每个节点 判断 他下面么有挂载单词的节点 了 就认为 下面的 都没用了 那么就设置为 nil。
只要递归玩得好,代码实现 也是很简单的
//将被删除的节点清除掉 func adjust(root *trieNode,ptr *trieNode,key byte,deep int){ //如果 没有next了 并且 这个节点 没有 记录单词 if len(root.next) == 0 && root.isWord == false{ deepSearchforDelete(ptr,nil) delete(ptr.next,key) return }else if len(root.next) == 0{ return } //如果 是 单词记录节点 for k,v := range root.next{ if deep == 0{ key = k } //记录下这个节点 if root.isWord { ptr = root //记录父节点 key = k//记录子节点 key } adjust(v,ptr,key,deep + 1) } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
这里每次遇到单词节点 就记录下,如果 到达最后一个节点且最后一个节点 没有 isword 那么 就从 上一个 isword 处的next删除这一段。这里 我们 递归 有 3个参数 一个 不用多说 就是递归子节点,另 2 各参数 是用来保存 上一个 单词节点的 子节点,然后是要删除的key。
自动索引功能: 你打代码时 不是IDEA 经常 有自动提示吗,还有搜索引擎。
这里我们也实现下吧,其实 还是很简单的
首先是查找节点,然后把节点下所有的 单词打出来 这两个功能在 前面 已经分别实现过了。只要 把它们组合在一起就好啦。
/** * Created by @CaomaoBoy on 2020/3/17. * email:<115882934@qq.com> */ type trieNode struct { isWord bool//是否单词结尾 next map[byte]*trieNode //子节点 } type Trie struct{ size int //大小 root *trieNode //根节点 } //初始化 Trie树 func NewTrie() *Trie{ node := trieNode{ isWord: false, next: make(map[byte]*trieNode,26), } a := Trie{ size: 0, root: &node, } return &a } //如果存在插入 func(trie *Trie) InsertIfContains(content string) bool{ if !trie.Contains(content){ trie.Insert(content) return true } return false } //往 节点内 添加内容 func(trie *Trie) Insert(content string){ if content == ""{ panic("error!") } if trie.root == nil{ node := trieNode{ isWord: false, next: make(map[byte]*trieNode,0), } trie.root = &node } rootnode := trie.root.next var cur *trieNode for i,v := range []byte(content){ var tmpnode *trieNode //如果cur为 nil if cur == nil{ if rootnode[v] == nil{ tmpnode = &trieNode{ isWord: false, next: make(map[byte]*trieNode,0), } //如果是字符串 结尾 if len(content) -1 == i{ tmpnode.isWord = true trie.size ++ } cur = tmpnode rootnode[v] = cur }else{ cur = rootnode[v] } //如果 cur 已经被初始化 }else { if cur.next[v] == nil{ tmpnode = &trieNode{ isWord: false, next: make(map[byte]*trieNode,0), } //如果是字符串 结尾 if len(content) -1 == i{ tmpnode.isWord = true trie.size ++ } cur.next[v] = tmpnode cur = tmpnode }else{ cur = cur.next[v] //如果是字符串 结尾 if len(content) -1 == i{ cur.isWord = true trie.size ++ return } } } } } //是否包含 str func (trie *Trie) Contains(content string) bool{ if trie.root == nil{ panic("error nil") } var cur *trieNode for i,v := range []byte(content){ if cur == nil{ //第一次 从root的next子节点获取 cur = trie.root.next[v] }else{ //当前节点 的next子节点里获取 cur = cur.next[v] } //如果 没有 获取到 认为 没有 if cur == nil{ return false } //如果已经 到达了最后一个节点 但是这个节点没有被标记成 单词 if len(content) -1 == i && cur.isWord == false{ return false } } return true } //遍历查找所有节点内容 func(trie *Trie) Search(deep int){ if trie.root == nil{ panic("root nil") } //res := make([][]byte,0) //deepSearch(trie.root,0,&res) //for _,v := range res{ // fmt.Println(string(v)) //} deepSearchx(trie.root,deep,nil) } 深度优先遍历 //func deepSearch(root *trieNode,deep int,res *[][]byte) []byte{ // if root.isWord{ // return nil // } // for k,v := range root.next{ // tmp := make([]byte,0,0) // tmp= append(tmp, k) // tmp = append(tmp, deepSearch(v, deep+1, res)...) // if deep == 0 { // *res = append(*res, tmp) // continue // }else{ // fmt.Println(string(tmp)) // return tmp // } // // // } // return nil //} //深度优先遍历 func deepSearchx(root *trieNode,deep int,res []byte) { if root.isWord{ fmt.Println(string(res)) } for k,v := range root.next{ //搜索深度 if deep == 0 && deep != -1{ return } tmp := make([]byte,0,0) tmp = append(tmp,res...) tmp =append(tmp,k) deepSearchx(v, deep -1, tmp) } } //用来输出显示 func deepSearchforDelete(root *trieNode,res []byte) { if len(root.next) == 0{ fmt.Println("clear:",string(res)) } for k,v := range root.next{ tmp := make([]byte,0,0) tmp = append(tmp,res...) tmp =append(tmp,k) deepSearchforDelete(v, tmp) } } //是否包含 str func (trie *Trie) Delete(content string) bool{ if trie.root == nil{ panic("error nil") } var cur *trieNode for i,v := range []byte(content){ if cur == nil{ //第一次 从root的next子节点获取 cur = trie.root.next[v] }else{ //当前节点 的next子节点里获取 cur = cur.next[v] } //如果 没有 获取到 认为 没有 if cur == nil{ return false } //如果已经 到达了最后一个节点 但是这个节点没有被标记成 单词 if len(content) -1 == i && cur.isWord == false{ return false } } cur.isWord = false//找到了 就删除 trie.Adjust()//删除没用节点 return true } //将被删除的节点清除掉 func(trie *Trie) Adjust(){ adjust(trie.root,trie.root,0,0) } //将被删除的节点清除掉 func adjust(root *trieNode,ptr *trieNode,key byte,deep int){ //如果 没有next了 并且 这个节点 没有 记录单词 if len(root.next) == 0 && root.isWord == false{ deepSearchforDelete(ptr,nil) delete(ptr.next,key) return }else if len(root.next) == 0{ return } //如果 是 单词记录节点 for k,v := range root.next{ if deep == 0{ key = k } //记录下这个节点 if root.isWord { ptr = root //记录父节点 key = k//记录子节点 key } adjust(v,ptr,key,deep + 1) } } //自动提示 func(trie *Trie) Suggess(content string){ if trie.root == nil{ panic("error nil") } var cur *trieNode for i,v := range []byte(content){ if cur == nil{ //第一次 从root的next子节点获取 cur = trie.root.next[v] }else{ //当前节点 的next子节点里获取 cur = cur.next[v] } //如果 没有 获取到 认为 没有 if cur == nil{ fmt.Println("no srarch") } //如果已经 到达了最后一个节点 但是这个节点没有被标记成 单词 if len(content) -1 == i { deepSearchx(cur,-1,nil) } } } func main(){ t := NewTrie() t.Insert("caomao") t.Insert("triemap") t.Insert("tEST00001") t.Insert("tEST0") t.Insert("SADASDASDSADASD") t.Search(20) t.Insert("apple"); t.Insert("app"); fmt.Println(t.Contains("app")) fmt.Println(t.Contains("tEST0")) fmt.Println(t.Contains("apple")) t.Delete("app") fmt.Println(t.Contains("apple")) t.Suggess("tE") }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
初步测试了下,代码应该没什么大问题,由于 随便写的 逻辑应该没问题,代码比较粗糙,随便写的 也没借鉴别人的代码。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/994741
推荐阅读
相关标签
