[Data Structure]Trie

Trie是用来做string存储和search的数据结构。Trie对比哈希有很多优点，第一是空间少，因为trie存储的时候是share prefix的，第二点是一般Trie比哈希更快，因为不用处理collision，尤其是在string很多的情况下。Trie的插入删除与查找的时间复杂度都是O(n)，n为给定string的长度。以下是我们实现的Trie支持的操作：

• public void put(String key, Value val)
• 插入一个string和对应的value
• public Value get(String key)
• 得到string对应的value，不在trie里的话返回null
• public boolean containsKey(String key)
• trie是否含有查询的string
• private Node delete(Node node, String key, int len)
• 在trie里删除string，如果string不在trie里的话，什么也不会改变
• public Iterable<String> keys()
• 返回trie里所有的key
• public Iterable<String> keysWithPrefix(String prefix)
• 返回trie里所有以prefix开头的key
• public String longestPrefixOf(String key)
• 找到查询string和trie里所有string的最长公共前缀
• public String longestKeyAsPrefixOf(String key)
• 找到查询string和trie里所有string的最长公共前缀，并且前缀要是trie里的单词

下面我们来分析每一个方法的实现：

首先我们要明确trie里每一个字符是存在edge上而不是node上，换句话说是隐式的存在node上的map里。每一个node包含存value的变量和一个map，map的key是字符，value是子节点。如果node对应的val不是null的话，就说明从root到当前节点组成的string是在trie中的。

1. put：

• 如果当前node不是null
• 如果还没有到stirng的末尾(index < s.length())，把对应的字符和子节点放入map
• 如果到了string的末尾，更新value
• 如果当前node是null，创建新node
• 如果还没有到stirng的末尾(index < s.length())，把对应的字符和子节点放入map
• 如果到了string的末尾，更新value

2. get:

按照每个字符去找相应的子节点即可，看最后能不能找到。

3. containsKey:

类似get

4. delete

• key 在 trie 里
• 如果当前 index 等于 key 的长度
• 如果当前节点有子结点，把 value 设置为 null，return 当前 node
• 如果当前节点没有子节点，return null
• 如果当前 index 小于 key 的长度，子节点的 return 值不为 null，return 当前 node
• 如果当前 index 小于 key 的长度，子节点的 return 值为 null
• 如果当前节点只有一个子节点并且 value 为 null，return null
• 如果当前节点有大于一个子节点，删除要截止在这，更新map，return 当前 node
• 如果当前节点 value 不为 null，删除要截止在这，更新map， return 当前 node
• key 不在 trie 里
• 如果当前 node 等于 null，return null
• 如果当前  index 等于 key 的长度，value 等于 null，return 当前 node
• 如果当前  index 小于 key 的长度
• 如果子节点 return 的值不为 null，return 当前 node
• 如果子节点 return 的值为null，为了确定子节点是本来就不存在还是被删除了，我们去 map 里找对应的 character
• 如果找到了，说明是子节点原本是存在的，就按照 key 在 trie里相应的方法删除
• 如果找不到，说明子节点原本就不存在，key 是 不在 trie 里的，return 当前 node

值得一提的是，trie 的删除操作真正执行删除的操作是 value 赋值为 null，或者更新 map

5. keys

本质上就是一个dfs，如果存的 map 是 tree map，输出可以按照 lexicographical 的顺序

6. keysWithPrefix

先按照prefix get node，然后 dfs

7. longestPrefixOf

根据当前的单词一步一步找就行，直到长度等于 key 的长度，或者没有子节点了

8. longestKeyAsPrefixOf

类似longestPrefixOf，只需要加一个变量记录当前遇到的最长的 key 的长度就行

Trie的完整代码如下：