【图解算法】Trie树
Trie树，字符串查找树
欢迎来到我的算法专栏，今天我们来讲一种常见的数据结构：Trie树。
我们会对Trie树的性质，相关操作，应用进行讲解，并模拟实现一个简版的Trie树。
目录
1. Trie树 简介
Trie 树，又叫做单词查找树，它由字符串中的所有字符构造而成，且允许我们使用被查找键中的字符进行查找。
它的英文单词trie来自于E.Fredkin在1960年玩的一个文字游戏，因为这个数据结构的作用是取自于(retrieval)数据，但是发音为try是为了与tree相混淆。
我首先会描述单词查找树的性质，包括查找和算法，然后详细学习它的数据表示方法和c++实现。
2. Trie树的基本性质
2.1 基本结构
我们直接看图：
可以看出，对于一个Trie树节点来说，一个节点存储一个字符，除此之外还存储当前路径中以自己为结尾的单词的数量。这个值得作用在于如果我们插入Trie中已经存在的单词的时候，准确记录其数量
当然，对于这个值得含义也有其他的说法，比如代表单词的编号。但是我觉得我这种理解更加的有用与简单（毕竟我们要运用于实战）。
2.1 存储方式
虽然我们的图画的十分简单，但是实际上程序中实际构造出的数据结构并不太一样。而我们面对的首要问题就是：如何通过一个节点找到下一个节点
我还是通过画图来展现：
根据上图，我们可以直观的认识到：
- 每个节点维护着26个空间（下文称为链接），每个空间对应一个字母
- 我们是将字符串和字符 隐式维护起来的（就是说没有直接用变量存储字符或字符串）
我们根据图来还原一下查找sea的过程：
- 根节点的第19个空间（指向所有s开头的单词组成的子单词查找树） 非空
- 第二个节点的第5个空间（指向所有以se开头的单词组成的子单词查找树）非空
- 第三个节点的第1个空间 （指向所有以sea开头的单词组成的子单词查找树）非空
这也印证了我之前的说法，数据结构不会存储任何字符与字符，它只保存了链接数组和值。由此，我们可以写出节点结构：
const int N = 26;
struct TrieNode {
int _val;
vector<TrieNode*>_next;
TrieNode(int val=0)
:_val(val)
{
_next.resize(N);
}
};
这里的N ,是可以更改的，不仅仅是字母，只要是字符，我们就可以使用Trie树；来操作。我们将基于含有N个字符的字母表的单词查找树叫做 N向单词查找树。
3. 相关接口
3.1 查找操作
在Trie树中查找单词是一个很简单的过程。
从根节点开始，首先进过单词首字母对应的链接，在下一个节点中沿着第二个字符对应的链接继续，在第二个节点中沿着第三个字符所对应的链接向前，如此这般找到最后一个字符所指向节点 或者遇到空链接。
如果找到，我们返回 当前单词数量，没找到就返回0.
int find(const string& s) {
Node* cur = &root;
for (int i = 0; i < s.size(); i++) {
int u = s[i] - 'a';
if (cur->_next[u] == nullptr)return 0;
cur = cur->_next[u];
}
return cur->_val;
}
3.2 插入操作
对于插入操作，我们采用边查找边插入的方式，可能会有两种情况：
- 到达单词尾之前就遇见空链接，这表示单词查找树中不存在于单词的尾字符对应的节点，因此需要为单词中还没有检查的每一个字符创建一个对应的节点并将结尾节点的值附为1.
- 在遇见空链接之前就已经到达单词尾部，此时我们只需要将结尾节点的值加1.
//插入单词
void insert(const string& s) {
Node* cur = &root;
for (int i = 0; i < s.size(); i++) {
int u = s[i] - 'a';
if (cur->_next[u] ==nullptr) {
cur->_next[u] = new Node();
}
cur = cur->_next[u];
}
cur->_val++;
}
3.3 删除操作
对于删除节点，我们有几个步骤：
- 将记录单词数量的值 置零
- 如果置零之后，该节点含有一个非空链接指向某个节点那么操作结束。 反之如果它的链接都是空，那么就删除这个节点。以此类推，最多到根节点。
void _erase(Node** node, const string& s, int d) {
if (!*node)return;
if (d == s.size()) {
(*node)->_val = 0;
}
else
{
int u = s[d] - 'a';
_erase(&((*node)->_next[u]), s, d + 1);
}
if ((*node)->_val)return;
for (char c = 0; c < 26; c++) {
if ((*node)->_next[c])return;
}
delete* node;
*node = NULL;
}
//删除单词
void erase(const string& s) {
//Node& tmp = root;
Node* tmp = &root;
_erase(&tmp,s, 0);
}
3.4 前缀检索
前缀查找是一种范围查找，比如我们想找所有以“ab”开头的单词，就可以使用前缀查找。
//前缀检索
//采集函数，将所有的结果存入数组
void collect(Node* node, string key, vector<string>& ans) {
if (!node)return;
if (node->_val)ans.push_back(key);
for (int i = 0; i < 26; i++) {
char ch = i + 'a';
collect(node->_next[i], key + ch, ans);
}
}
//第二种查找函数，返回当前节点地址
Node* _find(Node* node, const string& s, int len) {
if (!node)return NULL;
if (len == s.size()) {
return node;
}
return _find(node->_next[s[len] - 'a'], s, len + 1);
}
//前缀搜索
vector<string> KeysWithPrefix(const string& key) {
vector<string>ans;
Node* begin = _find(&root, key, 0);//找到前缀结束位置
collect(begin, key, ans);
return ans;
}
3.6 查看所有的单词
Trie树虽然长的比较奇怪，但其实就是一个多叉树。我们遍历一遍树，只要遇到节点的值大于0，就把从根节点到该节点的字符收集起来。再说明白一点，就是一个dfs.
//查看所有单词
vector<string> getAll() {
string path;
vector<string> ans;
_getAll(&root, path, ans);
return ans;
}
void _getAll(Node* node, string& path,vector<string>& ans) {
if (!node)return;
if (node->_val) {
ans.push_back(path);
}
for (int i = 0; i < 26; i++) {
path.push_back(i + 'a');
_getAll(node->_next[i], path, ans);
path.pop_back();
}
}
3.5 清空全树
//清空全树
void MakeEmpty() {
for (int i = 0; i < 26; i++) {
if ((&root)->_next[i]){
_empty(&((&root)->_next[i]));
}
}
}
void _empty(Node**node) {
for (int i = 0; i < 26; i++) {
if ((*node)->_next[i]) {
_empty(&(*node)->_next[i]);
}
}
delete *node;
*node = NULL;
}
4. 实际运用
- 在我们做题的时候，如果按照上面的写法，比较繁琐，所以这里提供一个更加简单的实现方式。
- 做题中，常见的运用主要集中在插入和查找上。
4.1 如何快速构造Trie树
我们可以使用数组来模拟实现Trie树。(来源:AcWing)
我们设计一个二维数组 son[N] [26] 来模拟整个树的结构，而cnt[N] 来记录单词个数。
这样其实是比较抽象的，我们举个例子： son[1][1]=2 代表的是 1号节点 的一个值为b的节点 是 2号节点。而son[1][0]=0 则表示1号节点不存在 值为 a 的节点。
我们也可以画个图，对于下图：
/Trie树快速存储字符集合和快速查询字符集合
#include <iostream>
using namespace std;
const int N = 100010;
//son[][]存储子节点的位置，分支最多26条；
//cnt[]存储以某节点结尾的字符串个数（同时也起标记作用）
//idx表示当前要插入的节点是第几个,每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];
void insert(char *str)
{
int p = 0; //类似指针，指向当前节点
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a'; //将字母转化为数字
if(!son[p][u]) son[p][u] = ++idx; //该节点不存在，创建节点
p = son[p][u]; //使“p指针”指向下一个节点
}
cnt[p]++; //结束时的标记，也是记录以此节点结束的字符串个数
}
int query(char *str)
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
if(!son[p][u]) return 0; //该节点不存在，即该字符串不存在
p = son[p][u];
}
return cnt[p]; //返回字符串出现的次数
}
int main()
{
int m;
cin >> m;
while(m--)
{
char op[2];
scanf("%s%s", op, str);
if(*op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}
4.2 最大异或对
在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
这算是一个比较隐蔽的 trie树问题。
如果我们使用暴力解决，那么时间复杂度为O(N^2),如果使用 tire树，那么时间复杂度为O(N);
那么这题我们该如何思考：
首先 ，我们取得最大异或（同0异1）结果的条件是什么？当然是 数字A与数字B的二进制下0->30位（最高位是符号位不用考虑）每一位都不相同，就算不能每一位都不一样，也应该使不一样的位数最大。
意识到这一点，我们就可以尝试使用二进制位建一颗Trie树：
我们以1,2,4为例子：
接下来，我们只需要依次拿着 1,2,4 去树中找出 最大值。
我们以4为例子：
我们想要的就是尽可能与4的每一位都不同的字符串，而我们有的字符串都在trie里了
- 4第二位是 1, 所以我们向左 找0
- 4第一位是 0, 所以我们向右，找1
- 4第零位是 0，我们想找1，但是树中没有，只能向左找0，所以我们找到了2，即2与4异或最大。
#include<iostream>
using namespace std;
const int N=1e6+10,M=N*40;
int a[N];
int son[M][2];
int n,idx;
void insert(int x){
int p=0; //指向根
for(int i=30;i>=0;i--){
int u=(x>>i)&1;
if(!son[p][u])son[p][u]=++idx;
p=son[p][u];
}
}
int serach(int x){
int p=0,ret=0;
for(int i=30;i>=0;i--){
int u=(x>>i)&1;
if(son[p][!u]){
ret += 1 << i;
//ret=ret*2+!u;
p=son[p][!u];
}
else{
//ret=ret*2+u;
p=son[p][u];
}
}
//ret^=x;
return ret;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
insert(a[i]);
}
int ans=0;
for(int i=0;i<n;i++){
ans=max(ans,serach(a[i]));
}
cout<<ans;
return 0;
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
16
0- 0
已为社区贡献1条内容
所有评论(0)