字典树是用来做什么工作的?
比如现在有一份班级人名单，我们要写出一个程序查找某个人是否存在，可以很轻松的暴力搜索，对于每一个人名都进行字符串的匹配，看两个字符串是否相同。但是如果我们要写程序从某个省份的人名单中查找某个人是否存在呢？这时候暴力匹配效率低的缺点就体现出来。这种情况可以使用字典树来进行查找，加速搜索过程。
字典树是什么?
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。 ——百度百科
字典树的样子:
(鼠标画的很丑，大家见谅。)
如果不熟悉树形结构之前也没有学过字典树可能会看的一头雾水.
你可能会有以下两个问题:
1、为什么这颗树上的点的编号是如图的样子?
2、这颗树的边为什么是用一些字母来记录的?
插入操作解释了这两个问题
字典树的三个基本操作
用插入一些字符串，查找某个字符串是否存在的形式来讲解字典树操作。
插入操作
用向一本字典中插入新的单词为例子，假设这本字典只有小写字母，介绍怎么进行插入操作，字典树作为一种树形结构，拥有根节点，一般将根节点记为0。
然后介绍一些接下来用到的数组和变量的意义
trie[maxn][26]: 第一维表示当前点第二维表示边，trie数组的值表示当前的点连接边所能达
到的另一点的编号
vis[maxn]: 记录当前点以及之前点是否构成一个完整的单词
初始时刻字典中没有任何单词，这颗树是空的，只有一个根节点计做0,trie[][]数组也没有记录信息，将其中的所有值计做0。
重复以下操作:
1、查找当前点与对应字符连接的点是否已经编号
2、如果没有编号进行编号，然后将当前点移动到编号的一点；如果已经编号直接移动到这一点
3、查找到最后的字符时将这一点的编号vis值记录为true，代表这点以及之前是一个完整的单词。
现在向这颗空树中插入一个词apple为例。
从根节点开始查找看0节点通过a连接的点有没有编号，即查找trie[0][a]，trie[0][a] = 0，没有编号，此时加上这个点的编号，计做1，即trie[0][a] = 1。这时候树变成了下面的样子。
接下来查找下一个字符p，从刚才编号的1点开始看p指向的点有没有编号，trie[1][p] = 0，没有编号，加上这个点的编号，计做2，即trie[1][p] = 2,树变成下面的样子。
重复这样的操作可以得到下面的树，然后将5号点也就是单词字符最后指向的点的vis计做true，表示这一点以及之前是一个完整单词，完成这个单词的插入。
为了方便后边将vis标记true的点染成红色。
同样的方法向这颗树中插入bear为例。
从根节点0开始查找与b相连的点有没有编号，trie[0][b] = 0没有编号，加上这个点的编号，计做6。
从刚才标号的6节点查找与e边相连的点有没有编号，trie[6][e] = 0，没有编号加上这个点的编号，计做7。
从刚才标号的7节点查找与a边相连的点有没有编号，trie[7][a] = 0，没有编号加上这个点的编号，计做8。
从刚才标号的8节点查找与r边相连的点有没有编号，trie[8][r] = 0，没有编号加上这个点的编号，计做9，同时这是这个单词的最后一个字母，将这一点的vis值标记为true，完成这个单词的插入。
刚才插入的单词每一个字符都没有对应到已经编号的点，查找时trie[][] = 0，现在看一个有对应点的例子:
继续向这颗树中插入一个单词bed为例
从根节点0开始查找与b相连的点有没有编号，trie[0][b] = 6，已经编号了，不重复编号，而是直接利用以前储存的信息继续查找，下一次查找直接从6号节点开始；从6号节点查找与e相连的点有没有编号，trie[6][e] = 7，已经编号了，下一次查找直接从7开始；从7号节点查找与d相连的点有没有编号，trie[7][d] = 0，没有编号，将这一点编号为10，同时这是一个单词最后一个字符，将这个位置vis计做ture，得到下面这颗树。
同样的方法插入一个单词apply我们就得到文章开头时看到的那棵树。
代码部分
bool vis[maxn]; /// 记录当前点以及之前是否构成一个完整的单词
int trie[maxn][26];/// 第一维表示点第二维表示边
int k = 1; /// 用来给边做编号
char a[14]; /// 输入的单词
char b[14]; /// 查找的单词
inline void insert_trie() {
int len = strlen(a),pos = 0;
///测量出需要添加单词的长度，pos代表点的位置，每次添加都从0(根)开始
for(int i = 0; i < len; i++) {
int c = s[i] - 'a';
/// 利用字符的ASCII码来记录每一条边
if(!trie[pos][c]) trie[pos][c] = k++;
///trie[pos][c] == 0代表这条边后面是没有点的,如果这条边的后面是没点的,加上这一点
pos = trie[pos][c];
/// 更新下一次查找的位置
}
vis[pos] = true;
///查找结束之后将最后一个字符对应的点标记为真，代表这是一个完整的单词
}
查找操作
查找时需要重复以下操作:
1、从当前点开始查找对应字符指向的点是否编号，初始时刻当前点是根节点0。
2、如果指向的点是已经编号的，将当前点移动到这一点，继续查找，如果没有编号，说明字典树中没有这个单词的前缀，也就不可能有这个单词。
3、查找到这个单词的最后一个字符时判断，当前点的vis值是否记录为true，true代表字典树中有这个单词。
用查找apply举例：
初始时刻从0号节点开始查找；
查找trie[0][a]，trie[0][a] = 1，把当前点移动到1点，从1号节点开始查找；
查找trie[1][p]，trie[1][p] = 2，把当前点移动到2点，从2号节点开始查找；
查找trie[2][p]，trie[2][p] = 3，把当前点移动到3点，从3号节点开始查找；
查找trie[3][l]，trie[3][l] = 4，把当前点移动到4点，从4号节点开始查找；
查找trie[4][y]，trie[4][y] = 11，把当前点移动到11点，y已经是这个单词最后一个字符，判断vis[11]的值是否为true，true表示字典树中存在这个单词，false表示不存在，这样查找到了这个单词。
再用查找app这个单词为例:
前面和查找apply一样，最后一个字符p停止查找判断这个点的标记是否为true，标记为false没有查找到这个单词。
再举一个例子，查找bedroom：
前面依然是类似apply的查找，但是当查找字符r时发现10号节点与r连接的节点没有被标记过，那不存在一个前缀是bedr的单词，所以更不可能存在单词bedroom，此时直接退出查找即可。
代码部分
bool vis[maxn]; /// 记录当前点以及之前是否构成一个完整的单词
int trie[maxn][26];/// 第一维表示点第二维表示边
int k = 1; /// 用来给边做编号
char a[14]; /// 输入的单词
char b[14]; /// 查找的单词
inline bool search_tire() {
int len = strlen(temp),pos = 0;
///测量出需要查找的单词的长度，pos代表点的位置，每次查找都从0(根)开始
for(int i = 0; i < len; i++){
int c = temp[i] - 'a';
///利用字符的ASCII码来记录每一条边
if(!trie[pos][c]) return false;
///如果还没有查找到这个单词后面就没点了，那不可能存在这个单词
pos = trie[pos][c];
/// 更新下一次查找的位置
}
return vis[pos];
///查找到单词的最后一个字符，如果这个点是真，说明查找到这个单词，否则没找到。
}
删除操作
介绍一种最简单的删除操作：
每当输入一个需要删除的单词时，做查找的操作，查找到这个单词的最后一个字符，将这个字符对应节点的vis[]值计做fasle即可。
比如要从字典树中删除单词apple。
先做查找操作，查找到最后一个单词e，将e指向的点计做false，这样下次查找时apple时查找到e时它指向的节点是false，不会返回查找到这个单词。
京公网安备 11010502036488号