前缀树

前缀树（Trie），又称字典树或前缀树，是一种用于存储关联数组（键为字符串）的有序树形数据结构。其核心创新在于摒弃了传统哈希表或二叉查找树将完整键值存储在节点的做法，转而利用节点在树中的路径位置来唯一标识字符串。每个节点仅存储一个字符，且同一父节点下的子节点字符互不相同，从而天然地共享所有字符串的公共前缀。这种设计使得插入、查找和前缀匹配操作的时间复杂度从线性级 O(n) 显著降低至字符数级 O(m)，极大地提升了大规模字符串集合的处理效率。

在现代计算架构中，前缀树超越了单纯的字符串存储工具，演变为解决高并发、海量数据文本处理的关键组件。在搜索引擎领域，它是构建倒排索引、实现毫秒级词频统计与字典序排序的基础；在移动端与前端应用中，它是实现智能输入框自动补全、拼写纠错及模糊搜索的底层引擎；在网络基础设施中，它更是 BGP 路由表等大规模 IP 地址映射的优选结构。尽管其内存占用随节点数增加而增长，但通过路径压缩与动态内存管理技术，其查询性能优势使其在需要频繁前缀匹配的场景中不可替代。