文章目录
- 线段树
- Trie（字典树 / 前缀树）
- 添加字符串
- 查询字符串
- 查询前缀
- 总结
- Trie的局限性
线段树
线段树不是完全二叉树，
线段树是平衡二叉树
Trie（字典树 / 前缀树）
https://blog.csdn.net/johnny901114/article/details/80711441
Trie是多叉树。
Trie和字典的区别：如果有n个条目，使用字典查询（底层是二叉树），查询的时间复杂度为O（logn），而Trie
查询每个条目的复杂度，与字典中一共有多少条目无关，只与要查询的字符串长度w有关，时间复杂度为O（w）。
用Trie实现字符串查找，性能比集合好。
节点的定义：
复制代码
1
2
3
4
5class TrieNode: # Trie字典树的最基本单元Node的定义 def __init__(self): self.isword = False # 表示从根节点到该节点组成的字符串是否为一个word self.next = {} # 是一个映射（字典）(因为Trie是多叉树，每个节点有多个后继节点)
添加字符串
复制代码
1
2
3
4
5
6
7
8
9
10
11def add(self, word): # 往Trie中添加一个字符串，要把字符串拆成字符，将字符做成节点，加入Trie cur_node = self.root for ch in word: # 遍历字符串中的每个字符 if not cur_node.next.get(ch): cur_node.next[ch] = TrieNode() cur_node = cur_node.next[ch] if not cur_node.isword: # 当遍历完字符串时，先判断该字符串是否已经在Trie中了，确保不会添加重复的单词 cur_node.isword = True self.size += 1
查询字符串
查询Trie中是否包含某一个单词
复制代码
1
2
3
4
5
6
7
8def contains(self,word): # 查询Trie中是否包含某一个单词 cur_node = self.root for ch in word: if not cur_node.next.get(ch): return False cur_node = cur_node.next[ch] return cur_node.isword
查询前缀
在Trie中查找，是否有单词以prefix为前缀
复制代码
1
2
3
4
5
6
7
8def isPrefix(self, prefix): # 在Trie中查找，是否有单词以prefix为前缀 cur_node = self.root for ch in prefix: if not cur_node.next.get(ch): return False cur_node = cur_node.next[ch] return True
总结
Trie的局限性
Trie最大的问题：空间。
解决方法：
- 压缩字典树，压缩字典树就是将多个单节点压缩在一起，一定程度上节省了空间，但是维护的成本更高
- Ternary Search Trie（三分搜索字典树）
扩展：后缀树。
最后
以上就是冷艳曲奇最近收集整理的关于【玩转数据结构Part5】线段树/Trie(字典树)线段树Trie（字典树 / 前缀树）总结的全部内容，更多相关【玩转数据结构Part5】线段树/Trie(字典树)线段树Trie（字典树内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复