前缀树
是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
字典树又称为前缀树或Trie树，是处理字符串常见的数据结构。假设组成所有单词的字符仅是“a”~"z"，请实现字典树结构，并包含以下四个主要功能：
void insert(String word)：添加word，可重复添加。
void delete(String word)：删除word，如果word添加过多次，仅删除一次。
boolean search(String word)：查询word是否在字典树中。
int prefixNumber(String pre)：返回以字符串pre为前缀的单词数量。
思考：
字典树的介绍。字典树是一种树形结构，优点是利用字符串的公共前缀来节约存储空间。
基本性质：
字典树的基本性质如下：
- 根节点没有字符路径。除根节点外，每一个节点都被一个字符路径找到。
- 从根节点到某一节点，将路径上经过的字符连接起来，为扫过的对应字符串。
- 每个节点向下所有的字符路径上的字符都不同。
也不需要记，看了实现，很自然的性质就理解了。
每个结点内有一个指针数组，里面有二十六个指针，分别指向二十六个字母。
如果指向某个字母的指针为空，那就是以前没有遇到过这个前缀。
搜索的方法为：
(1) 从根结点开始一次搜索；
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
其他操作类似处理
插入也一样，只是转到某个子树时，没有子树，那就创建一个新节点，然后对应指针指向新节点即可。
我们给出定义就更清楚了：
-
public static class TrieNode {
-
public int path; //表示由多少个字符串共用这个节点
-
public int end;//表示有多少个字符串是以这个节点结尾的
-
public TrieNode[] map;
-
//哈希表结构，key代表该节点的一条字符路径，value表示字符路径指向的节点
-
public TrieNode() {
-
path = 0;
-
end = 0;
-
map = new TrieNode[26];
-
}
-
}
path和end都是有用的，接下来会说明
insert：
-
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'; //0~25
-
if (node.map[index] == null) {
-
node.map[index] = new TrieNode();
-
}//创建，继续
-
node = node.map[index];//指向子树
-
node.path++;//经过加1
-
}
-
node.end++;//本单词个数加1
-
}
-
public boolean search(String word) {
-
if (word == null) {
-
return false;
-
}
-
char[] chs = word.toCharArray();
-
TrieNode node = root;
-
int index = 0;
-
for (int i = 0; i < chs.length; i++) {
-
index = chs[i] - 'a';
-
if (node.map[index] == null) {
-
return false;//找不到
-
}
-
node = node.map[index];
-
}
-
return node.end != 0;//end标记有没有以这个字符为结尾的字符串
-
}
delete：
-
public void delete(String word) {
-
//如果有
-
if (search(word)) {
-
char[] chs = word.toCharArray();
-
TrieNode node = root;
-
int index = 0;
-
for (int i = 0; i < chs.length; i++) {
-
index = chs[i] - 'a';
-
if (node.map[index].path-- == 1) {//path减完之后为0
-
node.map[index] = null;
-
return;
-
}
-
node = node.map[index];//去子树
-
}
-
node.end--;//次数减1
-
}
-
}
prefixNumber：
-
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.map[index] == null) {
-
return 0;//找不到
-
}
-
node = node.map[index];
-
}
-
return node.path;//返回经过的次数即可
-
}
好处：
1.利用字符串的公共前缀来节约存储空间。
2.最大限度地减少无谓的字符串比较，查询效率比较高。例如：若要查找的字符长度是5，而总共有单词的数目是26^5＝11881376，利用trie树，利用5次比较可以从11881376个可能的关键字中检索出指定的关键字，而利用二叉查找树时间复杂度是O( log2n )，所以至少要进行log211881376=23.5次比较。可以看出来利用字典树进行查找速度是比较快的。
应用：
<1.字符串的快速检索
<2.字符串排序
<3.最长公共前缀：abdh和abdi的最长公共前缀是abd，遍历字典树到字母d时，此时这些单词的公共前缀是abd。
<4.自动匹配前缀显示后缀
我们使用辞典或者是搜索引擎的时候，输入appl，后面会自动显示一堆前缀是appl的东东吧。
那么有可能是通过字典树实现的，前面也说了字典树可以找到公共前缀，我们只需要把剩余的后缀遍历显示出来即可。
相关题目：
一个字符串类型的数组arr1，另一个字符串类型的数组arr2。
arr2中有哪些字符，是arr1中出现的？请打印。
arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印。
arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印arr2中出现次数最大的前缀。
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/83141560
- 点赞
- 收藏
- 关注作者
评论（0）