DSA - 前缀树 Trie
概念
前缀树(字典树、Trie) 是一个树型结构,是一个用空间换时间的数据结构,操作包括插入、查找和删除。一般用来存字符串,每一个节点代表字符串中的一个字符。
组成
根节点:无实际意义,只是维护一系列指针执行其他节点。
其他节点:每个节点代表一个字符,除了存储数据外还维护指向其他节点的指针。
节点的数据结构:可以自定义,看实际需要,比如
isEnd
是否最后一个节点,count
前缀出现的次数。
操作
插入
insert(word) {
let crawl = this.root
for (let char of word) {
// 将字母转换成对应的 0~25 下标
const index = this._char2Index(char)
// 如果当前字符没有对应的节点,那就新建一个节点
if (!crawl.pointers[index]) {
crawl.pointers[index] = this._getTrieNode('')
}
// 继续深入
crawl = crawl.pointers[index]
}
// 标识一下最后的节点,把 word 存在这里只是方式之一
// 也可以存储别的信息,看实际需求
crawl.value = word
}
查找
search(word) {
let crawl = this.root
for (let char of word) {
const index = this._char2Index(char)
if (!crawl.pointers[index]) return false
crawl = crawl.pointers[index]
}
// word 可能在 trie 中只是一个前缀,不是一个词
// 所以要判断一下当前节点是不是最后的节点,是则说明 word 存在
return !!crawl.value
}
删除
先去查找 word
,
如果找到的话:
先把最后一个节点的
value
清空,再判断它的
pointers
是否都是空指针:是,可以把这个节点删掉了
否,不用做什么
没找到的话,不用做什么
复杂度
Worst Case
说明
建树(space)
$O(n^{k})$
n 是字符集中字符个数,k 是字符串长度 (满 k 叉树的节点总数)
插入(time)
O(k)
k 是字符串长度
查询(time)
O(k)
k 是字符串长度
哈希表 vs 前缀树
哈希表
前缀树
相似
数组 + 链表
数组 + 指针
不同
需要哈希函数、需要处理哈希冲突
没有 key collision,但存空指针要消耗更多空间
优点
可能节省空间:如果我们要存的是一系列长得很像的词,由于公共前缀只需要存一次,因此整体来说可以节省一些存储空间。
快速前缀查询:如果我们想要查询哪些词以某个前缀开头,用前缀树效率会比较高。
缺点
一般情况下前缀树是比较消耗空间的:每个 ASCII 字符占用的空间是 1 个字节,而每个前缀树节点之间是通过指针连接的,在 64 位操作系统上,每个地址要占 8 个字节的空间。一般来说,公共前缀节省的空间还是不能抵消指针占用的空间。
一般语言都没有提供这种数据结构,需要自己实现。
应用
autocomplete
matching algorithms
spellchecker
radix sort
Last updated
Was this helpful?