字典树
683 字
3 分钟
字典树
数据结构
特点：字典树支持高效的前缀查找。其次，通过共享前缀来节省空间，多个以相同前缀开头的字符串只需存储一份前缀。再次，字典树的节点不直接存储完整的字符串，而是通过从根节点到该节点的路径构成字符串 最后，字典树支持插入、查找、删除和前缀匹配等多种操作 插入和查找操作的时间复杂度均为 O(m)，其中 m 是字符串的长度
结构定义：字典树通常由两个主要结构组成。首先是TrieNode（节点），每个节点包含一个子节点的映射（通常使用哈希表或数组）和一个布尔值 end，指示该节点是否为某个字符串的结尾。其次是Trie（字典树），它包含一个指向根节点的指针，所有字符串的插入和查找操作都从根节点开始
struct trie { int nex[100000][26], cnt; bool exist[100000]; // 该结点结尾的字符串是否存在
void insert(char *s, int l) { // 插入字符串 int p = 0; for (int i = 0; i < l; i++) { int c = s[i] - 'a'; if (!nex[p][c]) nex[p][c] = ++cnt; // 如果没有，就添加结点 p = nex[p][c]; } exist[p] = true; }
bool find(char *s, int l) { // 查找字符串 int p = 0; for (int i = 0; i < l; i++) { int c = s[i] - 'a'; if (!nex[p][c]) return 0; p = nex[p][c]; } return exist[p]; }};维护异或极值
XOR 异或 将数的二进制表示看做一个字符串，就可以建出字符集为 的 trie 树。
我们考虑在一个01字典树（每个节点是0或1）里插入所有数的二进制表示。比如要插入一个32位整数，就从高位到低位一位一位插。
插入过程：
- 从最高位（比如31位）往最低位0位走。
- 每一位如果是0，就走/建0儿子，否则走/建1儿子。
查询最大异或值的过程： 假设现在要查一个数x，想找集合中一个数，使得异或值最大。异或要大，意味着尽量在每一位上异或出1。怎么做？
- 从高位到低位一位一位走。
- 每一位，优先找跟x当前位不同的方向（因为1异或0 = 1，能让结果高位出现1）。
- 如果能走，就走异位；不能走，就只能走同位。
- 边走边计算异或值。
查询最小异或值的过程（比如如果需要）：
- 每一位，优先走跟x当前位相同的方向（因为0异或0=0，1异或1=0，结果小）。
- 走不了再走异位。
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
CF 957E Novice's Mistake 题解
数据结构与算法字符串乘法与数字乘法结果相同的 (a,b) 计数：通过收紧枚举上下界让暴力可过。
2
Grafana 可视化与监控
云原生与运维Grafana 的定位、常见数据源与 Grafana + Prometheus 经典监控链路。
3
微服务之间如何传递 trace
后端开发跨服务传递的是 trace 上下文而非 tracer：HTTP header、gRPC metadata 与 MQ 消息头的标准做法。
4
kubectl port-forward 端口转发
云原生与运维kubectl port-forward 转发 Pod/Service、让局域网访问以及常用排查命令。
5
Wooden Toy Festival 题解：二分答案与贪心验证
数据结构与算法三个雕刻师制作 n 个玩具的最小等待时间：二分答案 + 排序后贪心分配验证，附完整 C++ 代码。
随机文章随机推荐