Trie树

Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，例如，英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。

 

Trie的核心思想是用空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。当然，如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存，这也是trie树的一个缺点。

 

 

Trie树的性质

 

Trie树的基本性质可以归纳为：

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

 

 

Trie树的基本实现

 

字典树的插入和查找操作都非常简单，只需遍历一遍字符串。

• 当进行插入操作时，对于第i个字符，先找到相应的子树，若不存在则插入一个新节点。对于字符串的最后一个字符，在插入完成后，标记这是一个词的结尾。
• 当进行查找操作时，从根节点开始，读取字符串中的字符，然后找相应的子树。在读完所有的字符后，如果该节点被标记为词尾，则查找成功，否则查找失败。

 

实现代码

 

public class TrieTree {
	
	private Node root;
	
	public TrieTree() {
		root = new Node();	
	}
	
	public void insert(String str) {
		Node t = root;
		for (int i = 0; i < str.length(); i++) {
			if (t.nodes[str.charAt(i) - 'a'] == null) {
				Node node = new Node();
				t.nodes[str.charAt(i) - 'a'] = node;
			} 
			t = t.nodes[str.charAt(i) - 'a'];
		}
		t.isStr = true;
	}
	
	public boolean find(String str) {
		Node t = root;
		int i;
		for (i = 0; i < str.length() && t != null; i++) {
			t = t.nodes[str.charAt(i) - 'a'];
		}
		return (t != null && t.isStr);
	}
	
	private class Node {
		boolean isStr;
		Node[] nodes;
		
		Node() {
			isStr = false;
			nodes = new Node[26];
		}
	}
}

 

 

 

Trie树的高级实现

 

可以采用双数组（Double-Array）实现。利用双数组可以大大减小内存使用量。

 

 

Trie树的应用

 

Trie是一种非常简单高效的数据结构，但有大量的应用实例。

 

(1) 字符串检索

事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。

 

举例：

• 给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
• 给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若rob是不良单词，那么文本problem含有不良单词。

 

(2) 字符串最长公共前缀

Trie树利用多个字符串的公共前缀来节省存储空间，反之，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀。

 

举例：

• 给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少？

解决方案：

首先对所有的串建立其对应的字母树。此时发现，对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数，于是，问题就转化为了离线（Offline）的最近公共祖先（Least Common Ancestor，简称LCA）问题。

而最近公共祖先问题同样是一个经典问题，可以用下面几种方法：

1. 利用并查集（Disjoint Set），可以采用采用经典的Tarjan 算法；
2. 求出字母树的欧拉序列（Euler Sequence ）后，就可以转为经典的最小值查询（Range Minimum Query，简称RMQ）问题了；

 

(3) 排序

Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。

 

举例：

• 给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。

 

(4) 作为其他数据结构和算法的辅助结构

如后缀树，AC自动机等。

 

 

Trie树复杂度分析

• 插入、查找的时间复杂度均为O(N)，其中N为字符串长度。
• 空间复杂度是26^n级别的，非常庞大（可采用双数组实现改善）。

 

原文地址：http://dongxicheng.org/structure/trietree/