MPT树前置 - 前缀树

⭐️前缀树的结构

Trie 前缀树

是什么：是一种有序的多叉树，用于存储字符串，适合前缀匹配查询。

1. 每个节点代表一个字符
2. 根节点不存储字符
3. 路径代表一个字符串的前缀

Patricia Trie 压缩前缀树

是什么：是前缀树的变种，通过压缩路径使得树的高度不至于过高。

1. 每个节点可以存储字符串，而不是单个字符。
2. 如果树没有分叉，则可压缩成一个节点。

⭐️前缀树的特点

1. 适合前缀匹配：快速判断某个字符串是否已有单词的前缀
2. 节省存储空间：多个字符串共享前缀
3. 支持字典序输出：天然支持排序输出

   ⭐️前缀树的插入、删除、查找复杂度

4. 插入：O(n)
5. 查找：O(n)
6. 删除：O(n)

⭐️前缀树和merkle树的对比

作用：前缀树用于字符串前缀匹配，mekle树用于数据验证

⭐️前缀树的应用

1. 搜索引擎的自动补全
2. web服务器的路由匹配
3. 大量字符串的压缩存储