有关字典树的简单介绍

• 框架：

1. 简单介绍
2. 相关实现
3. 更多结构

• 简单介绍

字典树：
也叫前缀树，trie。 就是一种树结构，但与一般间的树的结构还是有点不同。
这种数据结构是处理 字符串问题 的一种特定结构。其性能只与 要处理的字符串的长度有关。

以下这张图片只是简单的描绘 这种数据结构在人看来是长什么样子。
(里面的p，e在代码里有介绍)

• 相关实现

先来看看 对于这种结构的一些要求

• 思路：
  在代码注释里

• 上代码：

    // 主要就是这个trie树的 节点结构 好用，一开始可能会理解不太清
	// 但是这个节点 画出来的话 不是刚好就是一个节点。 与后面的功能（主要增加）对比，画画示意图出来会比较好理解
	
	// 因为是只考虑 26个英文字母，不区分大小写
	// 一个节点， 他有26条途径，字母画在路径上，从路径到达另一个节点，这个节点存储着 2个信息：
	// 1. path ： 有几个单词有这个字母， 也就是这个字母被滑过了多少次，被经过了多少次
	// 2. end ： 这个字母是否是一个单词的结尾，为int型，不是就是0，是结尾 就是在原基础上+1（可以添加重复（相同）的单词）
	public static class TrieNode{
   
		int path;
		int end;
		TrieNode[] nexts;		// 用数组保存这些个路径。 也可以用KV结构，比如HashMap<Character, TrieNode>
		
		public TrieNode() {
   
			path = 0;
			end = 0;
			this.nexts = new TrieNode[26];	// 26个英文字母，不区分大小写
		} 
	}


    public static class Trie{
   
		private TrieNode root;
		
		public Trie() {
   
			this.root = new TrieNode();
		}
		
		public void insert(String word) {
   
			if(word == null) {
   
				return ;
			}
			
			char[] chs = word.toCharArray();
			TrieNode cur = root;
			
			for(int i = 0; i < chs.length; i++) {
   
				if( cur.nexts[chs[i] - 'a'] == null ) {
   
					cur.nexts[chs[i] - 'a'] = new TrieNode();
				}
				cur = cur.nexts[chs[i] - 'a'];
				cur.path++; 	
			}
			cur.end++;
 			
		}
		
		// 查找一个单词 在这个树中 出现了几次（这个单词被添加进去过几次）
		// 怎么加的就怎么找
		public int search(String word) {
   
			if(word == null) {
   
				return 0; 
			}
			
			char[] chs = word.toCharArray();
			TrieNode cur = root;
			
			for(int i = 0; i < chs.length; i++) {
   
				if( cur.nexts[chs[i] - 'a'] == null) {
   
					return 0;
				}
				cur = cur.nexts[chs[i] - 'a'];
			}
			return cur.end; 
		}
		
		
		// 查找 这个树中有多少个单词 是以 传入的单词 为前缀
		// 怎么加的就怎么找
		public int prefixNumber(String prefix) {
   
			if(prefix == null) {
   
				return 0;
			}
			
			char[] chs = prefix.toCharArray();
			TrieNode cur = root;
			
			for(int i = 0; i < chs.length; i++) {
   
				if( cur.nexts[chs[i] - 'a'] == null ) {
   
					return 0;
				}
				cur = cur.nexts[chs[i] - 'a'];
			}
			return cur.path; 	
		}
		
		// 删除一个单词
		// 怎么加的就怎么删， 只是稍微有一点不一样： 
		// 对于删的时候，相应path--时，减到0了，之后就不用看了，直接赋值为null即可。jvm会做垃圾回收...
		public void delete(String word) {
   
			if(word == null || search(word) == 0) {
   
				return ;
			}
			
			char[] chs = word.toCharArray();
			TrieNode cur = root;
			
			for(int i = 0; i < chs.length; i++) {
   
				cur.nexts[chs[i] - 'a'].path--;
				if( cur.nexts[chs[i] - 'a'].path == 0  ) {
   
					cur.nexts[chs[i] - 'a'] = null;
					return;
				}
				cur = cur.nexts[chs[i] - 'a'];
			}
			cur.end--; 
		} 
		
		
	}

• 更多结构
  对于字典树，这只是一种相对简单实现，优化方案还有
  压缩字典树（Compressed Trie）
  三叉搜索字典树（Ternary Search Trie）

  其他有关字符串的结构 还有 后缀树