trie经常用来存储大量的字符串，以供以后的快速查找。这里主要介绍01字典树，专门来存储大量的整数。除根节点外，所有的其他节点都存储0或者1。因此，从根节点到叶子节点的路径就是一个完整的二进制整数。在代码上，我们通常使用一个二维数组来表示这个数据结构，trie[MAXN][2]。用trie[i]表示第i个节点，trie[i][0]如果被赋值为非零，则表示trie[i]的拥有左孩子，且trie[i][0]表示左孩子的在数组中的序号，同理可得，trie[i][1]表示trie[i]的右孩子。如果trie[i][0]或trie[i][1]被赋值为0，表示trie[i]节点没有左孩子或者右孩子。
建树的代码如下：
const int MAXN = 10000 * 2 + 10;
/*
We use a 2D-array to store the trie tree. We take the i th node
in the tree as trie[i], and the value of the trie[i][0/1] is the serial number(index)
of its child node, i.e, not specifying trie[i][0/1] means that it has no child nodes.
Note: trie[0] is the root of the tree.
*/
int trie[MAXN][2];
int sz = 1;
void init() {
memset(trie, 0, sizeof(trie));
}
void insert(int n) {
int u = 0; // the index of the current node
for (int i = 30; i >= 0; i--) {
int c = (n >> i) & 1; // get the high bit
if (!trie[u][c]) trie[u][c] = sz++; // add a new node
u = trie[u][c];
}
}
查询的代码如下：
bool query(int n) {
int u = 0;
for (int i = 30; i >= 0; i--) {
int c = (n >> i) & 1;
if (!trie[u][c]) return false;
u = trie[u][c];
}
return true;
}
可以将该树存储的所有整数打印出来
int st[32], top = 0;
void pp(int depth = 0) {
if (trie[depth][0]) {
st[top++] = 0;
pp(trie[depth][0]);
}
if (trie[depth][1]) {
st[top++] = 1;
pp(trie[depth][1]);
}
if (!trie[depth][0] && !trie[depth][1]) {
for (int i = 0; i < top; i++) cout << st[i];
cout << endl;
}
top--;
}
应用：找到与给定整数拥有最大异或值的数
int find_with_max_xor(int n) {
int ans = 0, u = 0;
for (int i = 30; i >= 0; i--) {
int c = (n >> i) & 1;
ans = 2 * ans + (trie[u][c ^ 1] != 0);
u = trie[u][c ^ 1] ? trie[u][c ^ 1] : trie[u][c];
}
return ans;
}
bool query(int n) {
int u = 0;
for (int i = 30; i >= 0; i--) {
int c = (n >> i) & 1;
if (!trie[u][c]) return false;
u = trie[u][c];
}
return true;
}