什么是Trie树

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。如下图：

上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质：

1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符互不相同。

通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。
可以看出，Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个结点中。另外，两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做前缀树（Prefix Tree）。

优缺点

Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

优点

1. 插入和查询的效率很高，都为O(m)，其中 m 是待插入/查询的字符串的长度。
    * 关于查询，会有人说 hash 表时间复杂度是O(1)不是更快？但是，哈希搜索的效率通常取决于 hash 函数的好坏，若一个坏的 hash 函数导致很多的冲突，效率并不一定比Trie树高。
2. Trie树中不同的关键字不会产生冲突。
3. Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。
4. Trie树不用求 hash 值，对短字符串有更快的速度。通常，求hash值也是需要遍历字符串的。
5. Trie树可以对关键字按字典序排序。

缺点

1. 当 hash 函数很好时，Trie树的查找效率会低于哈希搜索。
2. 空间消耗比较大。

应用

###1、字符串检索检索
查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较：

* 如果沿路比较，发现不同的字符，则表示该字符串在集合中不存在。
* 如果所有的字符全部比较完并且全部相同，还需判断最后一个节点的标志位（标记该节点是否代表一个关键字）。

struct trie_node
{
bool isKey; // 标记该节点是否代表一个关键字
trie_node *children[26]; // 各个子节点
};

2、词频统计Trie树常被搜索引擎系统用于文本词频统计。

struct trie_node
{
    int count;   // 记录该节点代表的单词的个数
    trie_node *children[26]; // 各个子节点 
};

思路：为了实现词频统计，我们修改了节点结构，用一个整型变量count来计数。对每一个关键字执行插入操作，若已存在，计数加1，若不存在，插入后count置1。
注意：第一、第二种应用:字符串检索和词频统计也都可以用 hash table 来做。

3、字符串排序

Trie树可以对大量字符串按字典序进行排序，思路也很简单：遍历一次所有关键字，将它们全部插入trie树，树的每个结点的所有儿子很显然地按照字母表排序，然后先序遍历输出Trie树中所有关键字即可。

4、前缀匹配

例如：找出一个字符串集合中所有以ab开头的字符串。我们只需要用所有字符串构造一个trie树，然后输出以a->b->开头的路径上的关键字即可。
trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

5、作为其他数据结构和算法的辅助结构

如后缀树，AC自动机等。

Java 代码实现

我们可以看到，trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表，或者用数组来模拟动态。空间的花费，不会超过单词数×单词长度。（来源）

import java.util.ArrayList;
import java.util.List;
/**
 * 单词查找树
 * 
 * @author Jay Chang
 * @since 2012-06-13
 */
class Trie {
	/** 单词查找树根节点，根节点为一个空的节点 */
	private Vertex root = new Vertex();
	/** 单词查找树的节点(内部类) */
	private class Vertex {
		/** 单词出现次数统计 */
		int wordCount;
		/** 以某个前缀开头的单词，它的出现次数 */
		int prefixCount;
		/** 子节点用数组表示 */
		Vertex[] vertexs = new Vertex[26];
		/**
		 * 树节点的构造函数
		 */
		public Vertex() {
			wordCount = 0;
			prefixCount = 0;
		}
	}
	/**
	 * 单词查找树构造函数
	 */
	public Trie() {
	}
	/**
	 * 向单词查找树添加一个新单词
	 * 
	 * @param word
	 *            单词
	 */
	public void addWord(String word) {
		addWord(root, word.toLowerCase());
	}
	/**
	 * 向单词查找树添加一个新单词
	 * 
	 * @param root
	 *            单词查找树节点
	 * @param word
	 *            单词
	 */
	private void addWord(Vertex vertex, String word) {
		if (word.length() == 0) {
			vertex.wordCount++;
		} else if (word.length() > 0) {
			vertex.prefixCount++;
			char c = word.charAt(0);
			int index = c - 'a';
			if (null == vertex.vertexs[index]) {
				vertex.vertexs[index] = new Vertex();
			}
			addWord(vertex.vertexs[index], word.substring(1));
		}
	}
	/**
	 * 统计某个单词出现次数
	 * 
	 * @param word
	 *            单词
	 * @return 出现次数
	 */
	public int countWord(String word) {
		return countWord(root, word);
	}
	/**
	 * 统计某个单词出现次数
	 * 
	 * @param root
	 *            单词查找树节点
	 * @param word
	 *            单词
	 * @return 出现次数
	 */
	private int countWord(Vertex vertex, String word) {
		if (word.length() == 0) {
			return vertex.wordCount;
		} else {
			char c = word.charAt(0);
			int index = c - 'a';
			if (null == vertex.vertexs[index]) {
				return 0;
			} else {
				return countWord(vertex.vertexs[index], word.substring(1));
			}
		}
	}
	/**
	 * 统计以某个前缀开始的单词，它的出现次数
	 * 
	 * @param word
	 *            前缀
	 * @return 出现次数
	 */
	public int countPrefix(String word) {
		return countPrefix(root, word);
	}
	/**
	 * 统计以某个前缀开始的单词，它的出现次数(前缀本身不算在内)
	 * 
	 * @param root
	 *            单词查找树节点
	 * @param word
	 *            前缀
	 * @return 出现次数
	 */
	private int countPrefix(Vertex vertex, String prefixSegment) {
		if (prefixSegment.length() == 0) {
			return vertex.prefixCount;
		} else {
			char c = prefixSegment.charAt(0);
			int index = c - 'a';
			if (null == vertex.vertexs[index]) {
				return 0;
			} else {
				return countPrefix(vertex.vertexs[index], prefixSegment.substring(1));
			}
		}
	}
	
	/**
	 * 调用深度递归算法得到所有单词
	 * @return 单词集合
	 */
	public List<String> listAllWords() {
		List<String> allWords = new ArrayList<String>();
		return depthSearchWords(allWords, root, "");
	}
	/**
	 * 递归生成所有单词
	 * @param allWords 单词集合
	 * @param vertex 单词查找树的节点
	 * @param wordSegment 单词片段
	 * @return 单词集合
	 */ 
	private List<String> depthSearchWords(List<String> allWords, Vertex vertex,
			String wordSegment) {
		Vertex[] vertexs = vertex.vertexs;
		for (int i = 0; i < vertexs.length; i++) {
			if (null != vertexs[i]) {
				if (vertexs[i].wordCount > 0) {
					allWords.add(wordSegment + (char)(i + 'a'));
					if(vertexs[i].prefixCount > 0){
						depthSearchWords(allWords, vertexs[i], wordSegment + (char)(i + 'a'));
					}
				} else {
					depthSearchWords(allWords, vertexs[i], wordSegment + (char)(i + 'a'));
				}
			}
		}
		return allWords;
	}
}
public class Main {
	public static void main(String[] args) {
		Trie trie = new Trie();
		trie.addWord("abc");
		trie.addWord("abcd");
		trie.addWord("abcde");
		trie.addWord("abcdef");
		System.out.println(trie.countPrefix("abc"));
		System.out.println(trie.countWord("abc"));
		System.out.println(trie.listAllWords());
	}
}

一些实际应用

即时响应用户输入的AJAX搜索框时，就是Trie开始的。