有关字典树的简单介绍
- 简单介绍
- 相关实现
- 更多结构
字典树：
也叫前缀树，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）其他有关字符串的结构 还有 后缀树
