学习笔记——Tire树
简介
字典树,即Trie树,是一种常用的数据结构。比如一个单词“apple”,可以分为五个字母,一般以一个虚节点为起始节点,记为$root$,那么apple这个单词就可以表示为$root$->a->p->p->l->e,同理,$bad$就是$root$->b->a->d。字典树的优点在于其不仅增加单词的复杂度是线性的,其查询单词或前缀的复杂度也是线性的。就好像翻字典一样,先找第一个字母,再第二个,比盲目的大海捞针要快上许多。
一种错误的实现
之前我有想到过开一个二维的数组$tree$[字母][深度],来记录,比如bad就是tree[‘b’][0]=tree[‘a’][1]=tree[‘d’][2]=true。但是这样做会存在一个问题,比如我记录单词aa,ab,以及ba,那就会使得tree[‘a’][0],tree[‘b][0],tree[‘a’][1],tree[‘b’][1]=true,然后查询bb时就会出现“bb存在”的错误,然而“bb”是不存在的,所以这种表达方式会产生一些无中生有的交叉错误。
正常的实现方式(数组实现)
1 | 以一个例子来说明。 |
这里以01字典树为例。(即用字典树表示二进制,其他情况类似)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93struct Tree {
struct node {//表示一个节点
array<int, 2> next;//该节点的两个儿子(0或1)
int size = 0;//该节点被覆盖的次数,就是有多少个二进制数字经过该节点(删除数据时用到)
};
vector<node> tree;//字典树
vector<int>Data;//记录数组a
int N;
int now = 0;
inline void Add(int num) {/加入一个数字
bitset<33> bit = num;//先转化为二进制形式
int root = 0;//默认以0为我们的虚根
tree[root].size++;//0被覆盖
for (int i = 32; i >= 0; i--) {
int id = bit[i];
if (!tree[root].next[id])//如果覆盖过程种发现之前还未出现该节点
tree[root].next[id] = ++now;//新分配一个节点
root = tree[root].next[id]; //往下覆盖
if (root >= (int)tree.size() - 1)
tree.resize(root + 1);
tree[root].size++;//被覆盖到的节点覆盖数加1
}
}
inline void Insert() {
while (N--) {
int num;
cin >> num;
Add(num);
Data.emplace_back(num);
}
}
inline void Delete(const int&num)//删除 {
bitset<33> bit = num;
int root = 0;
tree[root].size--;//虚节点覆盖数减一
for (int i = 32; i >= 0; i--) {//类似增加
if (root >= (int)tree.size() - 1)
tree.resize(root + 1);
int id = bit[i];
root = tree[root].next[id];
tree[root].size--;
}
}
inline int getAns(const int& i,const int&j) {
bitset<33> bit = i + j;//求i+j的最大xor值
int Ans = 0;
int root = 0;
for (int index = 32; index >= 0; index--) {
if (root >= (int)tree.size() - 1)
tree.resize(root + 1);
int id = bit[index];
if (tree[root].next[!id] &&/*其子节点被覆盖数为0时,说明该节点为叶节点,走不了咯*/ tree[tree[root].next[!id]].size)//优先选择和当前为相反的,由于是高位到低位(高位权重大)。
Ans += (1 << index), root = tree[root].next[!id];//1 xor 0 = 1
else/* if (tree[root].next[id] && tree[tree[root].next[id]].size)*/
//这个条件可以去掉,因为建树时无论数字多大,都是建成33位,有前导0补足,所以每个数字二进制长度一样,所以一定有路。
root = tree[root].next[id];
}
return Ans;
}
void inline Input() {
cin >> N;
tree.resize(1);
Insert();
}
inline long long Query() {
int Ans = 0;//暴力枚举。。。
//从1到N,删两个点求最大,再加回去。。。
for (int i = 0; i < Data.size(); i++) {
for (int j = i + 1; j < Data.size(); j++) {
Delete(Data[i]); Delete(Data[j]);
Ans = max(Ans, getAns(Data[i], Data[j]));
Add(Data[i]); Add(Data[j]);
}
}
return Ans;
}
inline void Clear() {
tree.clear();
Data.clear();
}
};
int main() {
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
Ans.Input();
cout << Ans.Query() << endl;
Ans.Clear();
}
system("pause");
return 0;
}