字符串1：前缀树的使用

前缀树： Trie树，又称字典树、前缀树，是一种树形结构，是哈希树的变种，是一种用于快速检索的多叉树结构。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Trie树也有它的缺点,Trie树的内存消耗非常大。
怎么样创建一个前缀树？首先我们定义一个字符串‘abc’ ，那么它是怎么建立的呢
字符串1：前缀树的使用
我们再添加一个字符串‘bce’，在树上怎么添加呢，会在这棵树上看头结点的下面一个有没有是以b开头的，没有就开过一条路，有就直接拿来复用。

真正的用处：
我们可以在每个节点添加两个数据项，一个end表示字符串是以这个节点为结尾的，一个path表示这个节点被经过多少次。前缀树一般用于字符串的增删改查等这些功能。
代码：



public class Code_01_TrieTree {

	public static class TrieNode {
		public int path;
		public int end;
		public TrieNode[] nexts;//用这个来表示路
		//也可以使用hashmap的方式来表示
		//public hashmap<char,TrieNode>

		public TrieNode() {
			path = 0;
			end = 0;
			nexts = new TrieNode[26];//这里就直接假设a-z有26条路，每个节点都有26条路
		}
	}

	public static 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;
			int index = 0;
			for (int i = 0; i < chs.length; i++) {
				index = chs[i] - 'a'; //index表这26条路的那一条路
				if (node.nexts[index] == null) { 
					node.nexts[index] = new TrieNode();
				}
				node = node.nexts[index]; //跳到下面的那个节点依次查看
				node.path++; //经过的次数+1
			}
			node.end++;//一直到最后那个，end+1
		}
    //删除这个字符串
		public void delete(String word) {
			if (search(word) != 0) {
				char[] chs = word.toCharArray();
				TrieNode node = root;
				int index = 0;
				for (int i = 0; i < chs.length; i++) {
					index = chs[i] - 'a';
					if (--node.nexts[index].path == 0) { //如果这个字符的path已经变为0了，那么它后面的那些节点都可以直接删除了
						node.nexts[index] = null;
						return;
					}
					node = node.nexts[index];
				}
				node.end--;
			}
		}
      //查询是否有这个字符串
		public int search(String word) {
			if (word == null) {
				return 0;
			}
			char[] chs = word.toCharArray();
			TrieNode node = root;
			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 prefixNumber(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++) {
				index = chs[i] - 'a';
				if (node.nexts[index] == null) {
					return 0;
				}
				node = node.nexts[index];
			}
			return node.path;
		}
	}

	public static void main(String[] args) {
		Trie trie = new Trie();
		System.out.println(trie.search("zuo"));
		trie.insert("zuo");
		System.out.println(trie.search("zuo"));
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.insert("zuo");
		trie.insert("zuo");
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.insert("zuoa");
		trie.insert("zuoac");
		trie.insert("zuoab");
		trie.insert("zuoad");
		trie.delete("zuoa");
		System.out.println(trie.search("zuoa"));
		System.out.println(trie.prefixNumber("zuo"));

	}

}

代码里面的方法解析：
插入和查找就不细说了，可以看代码的注解。重点说一下这里面的删除操作。删除操作里面有一个情况。
字符串1：前缀树的使用

例如我要删除字符串kgftw，这里面当我遍历到f的时候我们会发现这里的path已经为0了，所以我们可以直接把后面的那些删除。
查找有多少是以这个字符串为前缀的思想，一样我们遍历到这个字符串的最后一个字符，看它的path就可以知道它被当成了多少次前缀。

字符串1：前缀树的使用

相关推荐