做题用到字典树，整理记录一下备忘。
1 Trie
Trie 别称字典树、前缀树，是一种用于存储动态集合、关联序列的有序数数据结构，其关键字通常是字符串。
一棵 Trie 的示例：
它有3个基本性质：
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
- 每个节点的所有子节点包含的字符都不相同
Trie 的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。通常用于串的快速检索、拼法检查等。
2. Patricia Trie
在 Trie 树中，将唯一的子节点与其父节点合并以达到优化空间的目的，即得到 Patricia Trie 压缩前缀树。Linux 内核中称作 Radix Tree。压缩前缀树在由字符串做 KEY 构建关联数组的场景中应用广泛，如 IP 路由选择、文档倒排索引等。
一棵 Patricia Trie 树的示例：
