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