脚本宝典收集整理的这篇文章主要介绍了Trie树，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

  字典树（Trie）是一个比较简单的数据结构，也叫前缀树，用来存储和查询字符串。例如：aa, aba, ba, caaa, cab, cba, cc可以用下图的方式来进行存储。

@H_126_4@

可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子，(1rightarrow 4rightarrow 8rightarrow 12)表示的就是字符串 caa。   以此题为例最大异或对。建树的代码如下：

int idx, son[3000010][2], cnt[100010];
int n, a[100010];

void Insert(int x) {
    int p = 0;
    for (int i = 30; ~i; i -- ) {
        int s = x >> i & 1;
        if (!son[p][s]) son[p][s] = ++ idx;
        p = son[p][s];
    }
}

int query(int x) {
    int p = 0, res = 0;
    for (int i = 30; ~i; i -- ) {
        int s = x >> i & 1;
        if (son[p][!s]) p = son[p][!s], res += 1 << i;
        else p = son[p][s];
    }
    return res;
}

trie树要明确两个问题：   (son[N][x])是什么， (idx)是什么？   首先(son[N][x])这是个二维数组。   第一维N是题目给的数据范围，像在trie树当中(N)需要自己计算，最大为(N * 26)（其实根本达不到这么大，举个简单的例子假设用0和1编码，按照前面的计算最大的方法应该是4乘2=8但其实只有6个结点）。   第二维x代表着儿子结点的可能性有多少，在本题中下一位只有(0)或者(1)两种情况所以为2。 而这个二维数组本身存的是当前结点的下标，就是(N)喽，所以总结的话(son[N][x])存的就是第N的结点的x儿子的下标是多少，然后(idx)就是第一个可以用的下标。

脚本宝典总结

以上是脚本宝典为你收集整理的Trie树全部内容，希望文章能够帮你解决Trie树所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。