[数据结构与算法]高级数据结构 -- Trie前缀树（字典树）

字典树又称为前缀树或Trie树，是处理字符串常见的数据结构。Trie经常被搜索引擎系统。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

假设组成所有单词的字符仅是“a”~"z"，请实现字典树结构，并包含以下四个主要功能：

void insert(String word)：添加word，可重复添加。
void delete(String word)：删除word，如果word添加过多次，仅删除一次。
int search(String word)：查询word是否在字典树中，返回word的个数。
int serachPrefix(String pre)：返回以字符串pre为前缀的单词数量。
?

实现代码如下：

package 树;
class TrieNode {
	public int pass;
	public int end;
	public TrieNode[] nexts;
	public TrieNode() {
		//pass表示经过包含这个字符的字符串的个次数
		pass = 0;
		//end表示以这个字符结尾的字符串的个数
		end = 0;
		//表示26个字母
		nexts = new TrieNode[26];
	}
}

public class Trie {
	private TrieNode root;

	public Trie() {
		root = new TrieNode();
	}
	
	public void insert(String word) {
		if (word == null) {
			return;
		} 
		char[] chs = word.toCharArray();
		TrieNode node = root;
		node.pass++; //经过的次数+1
		int index = 0;		
		for (int i = 0; i < chs.length; i++) {  //从左往右遍历字符
			index = chs[i] - 'a';               
			//如果没有这条路劲，则新建路径
			if (node.nexts[index] == null) {
				node.nexts[index] = new TrieNode();
			}
			//有则前往子路径
			node = node.nexts[index];
			node.pass++;
		}
		node.end++;//字符串结束，以该字符结尾的字符串数量+1
	}
	
	public int search(String word) {
		if (word == null) {
			return 0;
		}
		TrieNode node = root;
		char[] chs = word.toCharArray();
		int index = 0;
		for (int i = 0; i < chs.length; i++) {
			index = chs[i] - 'a';
			if (node.nexts[index] == null) { //没有改子路径，说明没有插入过该字符串
				return 0;
			}
			node = node.nexts[index]; 
		}
		return node.end; //返回以这个单词结尾的字符串的个数
	}
	
	public int searchPrefix(String pre) {
		if (pre == null) {
			return 0;
		}
		char[] chs = pre.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chs.length; i++) {
			if (node.nexts[index] == null) { //没有改子路径，说明没有插入过该字符串
				return 0;
			}
			node = node.nexts[index];
		}
		return node.pass; //返回以该字符串为前缀的字符串的数量
	}
	
	public void delete(String word) {
		int flag = search(word); //先查找
		if (flag == 0) {
			return;
		}
		char[] chs = word.toCharArray();
		TrieNode node = root;
		node.pass--;  //从根节点开始-1
		int index = 0;
		for (int i = 0; i < chs.length; i++) {  //从左往右遍历字符
			index = chs[i] - 'a';               
			if (--node.nexts[index].pass == 0) { //如果--pass == 0 ，说明后面路劲必定都要剪掉，直接node.nexts[index] 置为null，后面GC会自动回收剪掉的路劲
				node.nexts[index] = null;
				return;
			}
			node.pass--; //数量减一
			node = node.nexts[index];
		}
		node.end--; 已该字符结尾的字符串数量减一
	}
	
}

插入操作

以?{?"abc","abcd","abce","bcd","bcf","cde" }举例，将所有字符串插入后结果如下：

从根节点的pass值我们可以知道，一共插入了6个字符串

删除操作

?删除“abcd” 后：

?查询操作

以查询"abc" 为例子

?返回1，存在"abc"字符串，且数量为1

前缀查询操作

以查询"ab" 为例子

?返回pass==2，表示有两个字符串以ab为前缀