Trie 树
- 每个节点储存一个字母
- 每个节点可以被多个 key 共享
- Trie 树的节点也可以是个 Map
何时找不到 key
- 从 Trie 树上掉落
- 最后的节点是白色的 （染色法，给单词最后字母的节点染成蓝色），如果节点是 Map,则最后的节点有值
Trie API
void put(String key,Value val)Value get(String key)void delete(String key)boolean contain(String key)longPrefixOf(String s)int size()
基本的 Trie 树实现
- 根节点是个哨兵节点，R = 128 是 ASCII 码
- 每个节点包含三个内容：储存一个字母，一个储存所有孩子节点(R个)的Map,一个颜色
- char ch 是储存的 char, DataIndexedCharMap next 储存下一个所有孩子节点的Map(用于向下查找)，boolean isKey 是是否是最后一个字符
- 优化
- 字母可以省略，因为一个储存所有孩子节点(R个)的Map的key的位置就代表了对应的字母
- DataIndexedCharMap next 可以用 hash Table 实现
查找操作
- 键的尾字符对应的节点值为非空 -> 命中，返回尾节点对应的值
- 键的尾字符对应的节点值为空 -> 未命中
- 结束于一条空链接 -> 未命中
插入操作
- 到达尾字符未遇到空链接 -> 把值绑定
- 遇到空链接，为每个未检查到的字符创建节点