前缀树

前缀树

Trie (发音为 “try”) 或前缀树是一种树数据结构，用于检索字符串数据集中的键。这一高效的数据结构有多种应用

• 自动补全
• 拼写检查
• IP 路由 (最长前缀匹配)
• T9 (九宫格) 打字预测
• 单词游戏

---

还有其他的数据结构，如平衡树和哈希表，使我们能够在字符串数据集中搜索单词。为什么我们还需要 Trie 树呢？尽管哈希表可以在 O(1) 时间内寻找键值，却无法高效的完成以下操作：

• 找到具有同一前缀的全部键值。
• 按词典序枚举字符串的数据集。

Trie 树优于哈希表的另一个理由是，随着哈希表大小增加，会出现大量的冲突，时间复杂度可能增加到 O(n)，其中 n 是插入的键的数量。与哈希表相比，Trie 树在存储多个具有相同前缀的键时可以使用较少的空间。此时 Trie 树只需要 O(m) 的时间复杂度，其中 m 为键长。而在平衡树中查找键值需要 O(mlogn) 时间复杂度。

Trie 树的结点结构

Trie 树是一个有根的树，其结点具有以下字段：。

• 最多 R 个指向子结点的链接，其中每个链接对应字母表数据集中的一个字母。本文中假定 R 为26，小写拉丁字母的数量。
• 布尔字段，以指定节点是对应键的结尾还是只是键前缀。

public class Trie {
	private boolean is_string = false;
	private Trie[] next = new Trie[26];

	public Trie(){}

	public void insert(String word){//插入单词
		Trie root = this;
		for (char c : word.toCharArray()) {
			if (root.next[c - 'a'] == null) root.next[c - 'a'] = new Trie();
			root = root.next[c - 'a'];
		}
		root.is_string = true;
	}

	public boolean search(String word){//查找单词
		Trie root = this;
		for (char c : word.toCharArray()) {
			if (root.next[c - 'a'] == null) return false;
			root = root.next[c - 'a'];
		}
		return root.is_string;
	}

	public boolean startsWith(String prefix){//查找前缀
		Trie root = this;
		for (char c : prefix.toCharArray()) {
			if (root.next[c - 'a'] == null) return false;
			root = root.next[c - 'a'];
		}
		return true;
	}
}

虚假的前缀树

class Trie {
	private HashSet<String> words;
	private HashSet<String> pres;

	public Trie() {
		words = new HashSet<>();
		pres = new HashSet<>();
	}

	public void insert(String word) {
		words.add(word);
		for (int i = 1; i <=word.length() ; i++) {
			pres.add(word.substring(0,i));
		}
	}

	public boolean search(String word) {
		return words.contains(word);
	}

	public boolean startsWith(String prefix) {
		return pres.contains(prefix);
	}
}

例如：

211. 添加与搜索单词 - 数据结构设计
使用前缀树进行单词搜索

class WordDictionary {
	private static class Node{
		public boolean isWord;
		public Node[] next = new Node[26];
	}

	private Node node;

	public WordDictionary() {
		node = new Node();
	}

	public void addWord(String word) {
		Node root = node;
		for(char c : word.toCharArray()){
			if(root.next[c-'a'] == null)
				root.next[c-'a'] = new Node();
			root = root.next[c-'a'];
		}
		root.isWord = true;
	}

	/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
	public boolean search(String word) {
		Node root = node;
		return dfs(root,word,0);
	}

	private boolean dfs(Node cur,String word,int index){
		if(index == word.length()) return cur.isWord;
		if(word.charAt(index) != '.'){
			if(cur.next[word.charAt(index)-'a'] == null)
				return false;
			return dfs(cur.next[word.charAt(index)-'a'],word,index+1);
		}else {
			for(Node n:cur.next){
				if(n != null && dfs(n,word,index+1))
					return true;
			}
		}
		return false;
	}
}