[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的完整代码如下：

	public class Trie<Value> {
	private class Node {
	private Value val;
	private TreeMap<Character, Node> children;
	public Node() {
	val = null;
	children = new TreeMap<Character, Node>();
	}
	}
	private Node root;
	public Trie() {
	root = null;
	}
	public boolean containsKey(String key) {
	Node node = getNode(key);
	if (node == null)
	return false;
	return node.val != null;
	}
	public void put(String key, Value val) {
	root = put(root, key, val, 0);
	}
	private Node put(Node node, String key, Value val, int index) {
	if (node == null)
	node = new Node();
	if (index == key.length()) {
	node.val = val;
	return node;
	}
	Node next = put(node.children.get(key.charAt(index)), key, val, index + 1);
	node.children.put(key.charAt(index), next);
	return node;
	}
	public Value get(String key) {
	Node node = getNode(key);
	return node == null? null: node.val;
	}
	private Node getNode(String key) {
	int len = key.length();
	Node node = root;
	for (int i = 0; i < len; i++) {
	if (node == null)
	return null;
	node = node.children.get(key.charAt(i));
	}
	return node;
	}
	public void delete(String key) {
	root = delete(root, key, 0);
	}
	private Node delete(Node node, String key, int len) {
	if (node == null)
	return null;
	if(key.length() == len) {
	//it key is not a word in trie
	if (node.val == null)
	return node;
	else {
	//if the node has children
	if (node.children.size() > 0) {
	node.val = null;
	return node;
	} else
	return null;
	}
	}
	Node next = delete(node.children.get(key.charAt(len)), key, len + 1);
	if (next == null) {
	//if word is not in the trie
	if (!node.children.containsKey(key.charAt(len)))
	return node;
	else {
	//if has more the one children or this node has value(it is a word in trie)
	if (node.children.size() > 1 || node.val != null) {
	node.children.remove(key.charAt(len));
	return node;
	} else
	return null;
	}
	} else
	return node;
	}
	public Iterable<String> keys() {
	LinkedList<String> list = new LinkedList<String>();
	collect(root, list, "");
	return list;
	}
	private void collect(Node node, LinkedList<String> list, String str) {
	if (node == null)
	return;
	if (node.val != null)
	list.add(new String(str));
	Iterator<Entry<Character, Node>> iter = node.children.entrySet().iterator();
	while (iter.hasNext()) {
	Entry<Character, Node> entry = iter.next();
	collect(entry.getValue(), list, str + entry.getKey());
	}
	}
	public Iterable<String> keysWithPrefix(String prefix) {
	LinkedList<String> list = new LinkedList<String>();
	Node node = getNode(prefix);
	collect(node, list, prefix);
	return list;
	}
	public String longestPrefixOf(String key) {
	int length = search(root, key, 0);
	return key.substring(0, length);
	}
	private int search(Node node, String key, int len) {
	if (node == null)
	return len;
	if (key.length() == len)
	return len;
	Node next = node.children.get(key.charAt(len));
	if (next == null)
	return len;
	return search(next, key, len + 1);
	}
	public String longestKeyAsPrefixOf(String key) {
	int length = search(root, key, 0, 0);
	return key.substring(0, length);
	}
	private int search(Node node, String key, int longestLen, int currLen) {
	if (node == null)
	return longestLen;
	if (node.val != null)
	longestLen = currLen;
	if (key.length() == currLen)
	return longestLen;
	Node next = node.children.get(key.charAt(currLen));
	return search(next, key, longestLen, currLen + 1);
	}
	}

view raw trie.java hosted with ❤ by GitHub