字典树的定义

  • 在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。 与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。 一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。
  • 字典树
  • 像上图这个数,可以知道字典树的根是为空的,然后拥有相同父结点的子结点,它们都有相同的字符串前缀,可以观察一下是不是?
  • 利用字典树这样的特性,能帮助我们做什么能? 大家都用过中华字典吧,它也利用字典树这样的特性。可以帮我们高效存储和查找字符串, 工程上 trie树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

静态字典树

  • 根据题目的不同,我们一般会定义不同的trie树(字典树)。但是大致是不会变的。

  • 字典树的定义

    • 一般情况下都使用二维trie树。
    • 变量介绍
      • idx -> 模拟内存分配
      • trie[i][j] -> 结点 i 的子结点 j 是否有值,0表示没有值
      • cnt[i] -> 在字符串中 表示以 i 这个结点结尾的字符串的个数
  • 以两个例题为例,来了解字典树。

    1. 维护一个字符串集合,支持两种操作:I x 向集合中插入一个字符串 x;Q x 询问一个字符串在集合中出现了多少次。共有 N 个操作,输入的字符串总长度不超过 105,字符串仅包含小写英文字母。

      • 根据题目,可构建符合题意的字典树
        • 	const int N = 1e5 + 5; // 因为最坏的情况是 最长的链等于字符串长度
          	int trie[N][26], idx, cnt[N]; // 26 代表的是 26 个字符,cnt[N] 用来保存以某一点结束的字符串个数
          
      • 在字典树中插入字符串
        • 	void insert(string s) {
          		int p = 0; // 从根结点开始 
          		for (int i = 0; i < s.size(); ++ i) {
          			int u = s[i] - 'a'; // 算出该字符对应的子结点下标
          			if (trie[p][u] == 0) // 表示这里没有保存过字符,现在需要分配内存
          				trie[p][u] = ++ idx; // ++ idx 是因为 0 为根结点
          			p = trie[p][u];    // 到下一个结点,匹配下一个字符
          		}
          		cnt[p] ++;  // 循环结束后,说明这个字符串已经插入,是以 下标为 p 这个结点结尾 所以, 以该结点结尾的字符串数 +1
          	}
          
      • 查找对应字符串在字典树中出现了多少次
        • 
          	int query(string s) {
          		int p = 0;
          		for (int i = 0; i < s.size(); ++ i) {
          			int u = s[i] - 'a';
          			if (trie[p][u] == 0) return 0; // 只要有一个字符没有匹配到就说明不存在字符串					
          			p = trie[p][u];
          		}
          
          		return cnt[p]; // 找到字符串 以 p 结点结尾的字符串个数
          	}
          
      • 完整代码
        • 题目链接:Trie字符串统计

        • 
          	#include <iostream>
          	#include <string>
          	using namespace std;
          
          	const int N = 1e5 + 5;
          	int trie[N][26], cnt[N], idx;
          	string op, str;
          
          
          
          	void insert(string s) {
          		int p = 0; // 从根结点开始 
          		for (int i = 0; i < s.size(); ++ i) {
          			int u = s[i] - 'a'; // 算出该字符对应的子结点下标
          			if (trie[p][u] == 0) // 表示这里没有保存过字符,现在需要分配内存
          				trie[p][u] = ++ idx; // ++ idx 是因为 0 为根结点
          			p = trie[p][u];    // 到下一个结点,匹配下一个字符
          		}
          		cnt[p] ++;  // 循环结束后,说明这个字符串已经插入,是以 下标为 p 这个结点结尾 所以, 以该结点结尾的字符串数 +1
          	}
          
          	int query(string s) {
          		int p = 0;
          		for (int i = 0; i < s.size(); ++ i) {
          			int u = s[i] - 'a';
          			if (trie[p][u] == 0) return 0; // 只要有一个字符没有匹配到就说明不存在字符串					
          			p = trie[p][u];
          		}
          
          		return cnt[p]; // 找到字符串 以 p 结点结尾的字符串个数
          	}
          	int main() {
          	 int n;
          	 cin >> n;
          
          		while (n --) {
          		 cin >> op;
          		 if (op == "I") {
          			  cin >> str;
          			  insert(str);
          			} else if (op == "Q") {
          			 cin >> str;
          			 cout << query(str) << endl;
          			}
          		}
          	}
          
          
    2. 在给定的 N 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?

      • 根据题目要求定义字典树
        • 	const int N = 3e6 + 5; // 注意题目给的数据范围
          	int trie[N][2], idx; // 二位数组设置 2,表示 0 1 两种状态
          
      • 把整数以二进制串形式插入字典树
        • 	void insert(int x) {
          		int p = 0; // 从根结点开始
          		for (int i = 30; i >= 0; -- i) // 题目给的数据,0 <= Ai < pow(2,31)
          		{
          			int u = (x >> i) & 1; // 从最高位开始取,对应位的 0 1
          			if (trie[p][u] == 0)
          				trie[p][u] = ++ idx;
          			p = trie[p][u];
          		}
          	}
          
      • 查找字典树中的数和数x的最大异或和
        • 异或:二进制状态下,相同位,数值相同则该位为0,否则为1。 eq: 1000 xor 1111 = 0111

        • 所以要满足最优解,就应该尽可能的是异或出来的值最高位1更多。

        • 	int query(int x) {
          		int p = 0;
          		int ans = 0;
          		for (int i = 30; i >= 0; -- i) {
          			int u = (x >> i) & 1;
          			ans <<= 1; // 将答案左移动一位 相当于 ans * 2
          			if (trie[p][1-u] == 0) // 这里要找与x取出来的 数值相反的,如果不存在则该位异或出来的结果必然等于0
          				p = trie[p][u];
          			else {
          				ans += 1; // 存在相反的位异或出来的结果 等于 1
          				p = trie[p][1-u];
          			}
          
          		}
          		return ans;
          	}
          
      • 完整代码
        • 题目链接:最大异或对
        • 	#include <iostream>
          	#include <algorithm>
          	#include <string>
          	using namespace std;
          
          	const int N = 3e6 + 5;
          
          	int trie[N][2], idx, a[N];
          
          	void insert(int x) {
          		int p = 0; // 从根结点开始
          		for (int i = 30; i >= 0; -- i) // 题目给的数据,0 <= Ai < pow(2,31)
          		{
          			int u = (x >> i) & 1; // 从最高位开始取,对应位的 0 1
          			if (trie[p][u] == 0)
          				trie[p][u] = ++ idx;
          			p = trie[p][u];
          		}
          	}
          
          	int query(int x) {
          		int p = 0;
          		int ans = 0;
          		for (int i = 30; i >= 0; -- i) {
          			int u = (x >> i) & 1;
          			ans <<= 1; // 将答案左移动一位 相当于 ans * 2
          			if (trie[p][1-u] == 0) // 这里要找与x取出来的 数值相反的,如果不存在则该位异或出来的结果必然等于0
          				p = trie[p][u];
          			else {
          				ans += 1; // 存在相反的位异或出来的结果 等于 1
          				p = trie[p][1-u];
          			}
          
          		}
          		return ans;
          	}
          	int main() {
          		int n;
          		cin >> n;
          		for (int i = 0; i < n; ++ i) {
          		   cin >> a[i];
          		   insert(a[i]);
          		}
          
          	 int ans = -0x3f3f3f3f;
          		for (int i = 0; i < n; ++ i) {
          		    ans = max(ans, query(a[i]));
          	  }
          
          	  cout << ans << endl;
          	  return 0;
          	}
          

总结

  • 字典树的运用比较灵活,根据题目定义不同类型的字典树来解决问题。