MPT树前置 - 前缀树
- shawn_shaw
- 发布于 2025-04-13 05:37
- 阅读 404
⭐️前缀树的结构是什么：是一种有序的多叉树，用于存储字符串，适合前缀匹配查询。每个节点代表一个字符根节点不存储字符路径代表一个字符串的前缀⭐️前缀树的特点适合前缀匹配：快速判断某个字符串是否已有单词的前缀节省存储空间：多个字符串共享前缀支持字典序输出：天然支持排序输出⭐️
⭐️前缀树的结构
Trie 前缀树
是什么：是一种有序的多叉树，用于存储字符串，适合前缀匹配查询。
- 每个节点代表一个字符
- 根节点不存储字符
- 路径代表一个字符串的前缀
Patricia Trie 压缩前缀树
是什么：是前缀树的变种，通过压缩路径使得树的高度不至于过高。
- 每个节点可以存储字符串，而不是单个字符。
- 如果树没有分叉，则可压缩成一个节点。
⭐️前缀树的特点
- 适合前缀匹配：快速判断某个字符串是否已有单词的前缀
- 节省存储空间：多个字符串共享前缀
- 支持字典序输出：天然支持排序输出
⭐️前缀树的插入、删除、查找复杂度
- 插入：O(n)
- 查找：O(n)
- 删除：O(n)
⭐️前缀树和merkle树的对比
作用：前缀树用于字符串前缀匹配，mekle树用于数据验证
⭐️前缀树的应用
- 搜索引擎的自动补全
- web服务器的路由匹配
- 大量字符串的压缩存储
- 学分: 0
- 分类: 以太坊
- 标签:
