Trie树 —— Trie 这个名字取自 “retrieval”，检索，因为 Trie 可以只用一个前缀便可以在一部字典中找到想要的单词。 虽然发音与 「Tree」 一致，但为了将这种 字典树 与 普通二叉树 以示区别，程序员小吴一般读 「Trie」 尾部会重读一声，可以理解为读 「TreeE」 。

Trie 树，也叫字典树、前缀树 （Prefix Tree）、单词查找树 或 键树。顾名思义，就是一个像字典一样的树。此外 Trie 树也称前缀树（因为某节点的后代存在共同的前缀，比如 pan 是 panda 的前缀）。

它是一种 专门处理字符串匹配 的数据结构，用来解决 在一组字符串集合中快速查找某个字符串的问题。

它的 key 都为字符串，能做到高效查询和插入，时间复杂度为 ，k 为字符串长度，缺点是如果大量字符串没有共同前缀时很耗内存。它的 核心思想 就是通过最大限度地减少无谓的字符串比较，使得查询高效率，即 「用空间换时间」 ，再利用共同前缀来提高查询效率。