深度解析Trie（字典树）

• 算法结构

目录

  • 一、Trie简介
  • 二、用数组实现Trie
  • 三、存储与查询
  • 四、应用：最大异或对
  • References

一、Trie简介

Trie，又称字典树或前缀树，常用来存储和查询字符串。假定接下来提到的字符串均由小写字母构成，那么Trie将是一棵

26

26

26 叉树。

给定五个字符串，分别为 acd、abd、be、cbe、cbf，Trie将以以下形式存储这些字符串：

深度解析Trie（字典树）

可以发现，这棵字典树用边来代表字母，而从根节点到树上某一节点的路径就代表了一个字符串。举个例子，

1

→

2

→

5

→

6

1\to2\to 5\to 6

1→2→5→6 表示的就是字符串 abd。

二、用数组实现Trie

前面提到过，Trie是一棵

26

26

26 叉树，假设我们要存储的所有字符串的总长度不超过

N

N

N，这意味着树中最多有

N

+

1

N+1

N+1 个节点（最坏情况下，每个字符串都单独形成了一条路径，最后算上根节点一共

N

+

1

N+1

N+1 个），保险起见，我们可以开一个二维数组 son[N + 10][26] 用来存储Trie。

那这个数组的含义是什么呢？如下图

深度解析Trie（字典树）

编号为

u

u

u 的节点指向了编号为

v

v

v 的节点，边对应了字母

c

c

c，反映到 son 数组中就是：

son[u][c] = v

由于下标只能是整数，所以我们将

a

∼

z

a\sim z

a∼z 映射为

0

∼

25

0\sim 25

0∼25。

例如，对于最开始提到的Trie，其对应的 son 数组为

son[1][0] = 2  // 即son[1][a] = 2
son[2][2] = 3  // 即son[2][c] = 3
son[3][3] = 4  // 即son[3][d] = 4
son[2][1] = 5  // 即son[2][b] = 5
son[5][3] = 6  // 即son[5][d] = 6
son[1][1] = 7  // 即son[1][b] = 7
son[7][4] = 8  // 即son[7][e] = 8
son[1][2] = 9  // 即son[1][c] = 9
son[9][1] = 10  // 即son[9][b] = 10
son[10][4] = 11  // 即son[10][e] = 11
son[10][5] = 12  // 即son[10][f] = 12

现规定从

0

0

0 开始对节点逐个编号，编号为

0

0

0 的节点是根节点（Trie为空时仅含根节点），同时 son 数组进行全0初始化。我们来看如何将字符

c

c

c 插入到Trie中。

如果 son[0][c] == 0 成立，说明Trie中不含字符

c

c

c，此时应当令 son[0][c] = idx，其中 idx 为新建立的节点的编号。否则，

c

c

c 已存在于Trie中，无需插入。

三、存储与查询

根据前面的讨论，我们不仅需要用 son 数组来存储Trie，还需要用 idx 来为每个节点编号。但，仅仅有这两个变量就足够了吗？

考虑这两个字符串：ab，abcd，显然，后者在Trie中形成的路径包含前者，所以在存储这两个字符串的时候仅会得到一条路径，那如何说明我们存储了两个字符串呢？很简单，只需在每个字符串的末尾打上标记，如下图所示：

深度解析Trie（字典树）

对应到代码中就是再开一个 cnt 数组（全0初始化），并令 cnt[2] = 1, cnt[4] = 1 即可。

如果同一个字符串存储了多次，只需在每次存储的时候执行 cnt[p]++ 即可，其中 p 是字符串末尾所对应的节点的编号。

到此为止，我们可以勾勒出Trie的雏形：

const int N = 1e5 + 10;

int son[N][26], cnt[N], idx;  // 声明为全局变量

⚠️ 若将其直接声明在结构体中，则由于结构体中的变量存储在栈区，会造成内存溢出，从而导致 Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)。

存储一个字符串的实现如下：

void insert(const string &s) {
    int p = 0;  // 初始时位于根节点
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        if (!son[p][c]) son[p][c] = ++idx;  // 如果节点不存在则创建节点
        p = son[p][c];  // 移动至下一个节点处
    }
    cnt[p]++;
}

查询操作的实现与存储类似，只需沿着路径移动即可：

int query(const string &s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        if (!son[p][c]) return 0;
        p = son[p][c];
    }
    return cnt[p];  // 返回字符串的个数
}

存储和查询的时间复杂度均为

O

(

len

(

s

)

)

O(\text{len}(s))

O(len(s))，其中

s

s

s 是字符串。

四、应用：最大异或对

原题链接：https://www.acwing.com/problem/content/description/145/

Trie不仅可以存储字符串，还能存储整数。在存储字符串时，Trie中的每条边对应了一个字符，在存储整数时，Trie中的每条边非

0

0

0 即

1

1

1，即Trie存储的是整数的二进制表示，此时Trie是一棵二叉树。

在存储一个整数时，一般是从它的最高位开始依次存储到最低位。例如，对于数字

5

5

5，它的二进制表示为

101

101

101，Trie将以以下形式存储：

深度解析Trie（字典树）

在存储多个整数的时候，我们无法确保所有数字的二进制位数都相同，所以需要找到二进制位数最多的那个数字，剩下的数字都要按照这个位数进行存储。例如，现有三个数字：

2

2

2，

4

4

4，

8

8

8，其二进制表示分别为

10

10

10，

100

100

100，

1000

1000

1000，但在存储的时候我们需要按照

0010

0010

0010，

0100

0100

0100，

1000

1000

1000 进行存储。

回到题目，因为

x

∈

[

0

,

2

31

)

x\in[0,2^{31})

x∈[0,231)，所以

x

x

x 的二进制表示最多有

31

31

31 位，由此可知所有的整数都需要按照

31

31

31 位的二进制数来存储。判断最高位是

1

1

1 还是

0

0

0 只需看 x >> 30 & 1 的值。

向Trie中插入一个整数的实现如下：

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

一个问题是，son 数组应该开多大？由于Trie是一棵二叉树，所以 son 数组的第二维的大小是

2

2

2，son 数组第一维的大小是Trie中所有节点的数量。考虑最坏的情形，每个整数都单独形成了一条路径，因此存储每个整数都需要

31

31

31 个节点，存储

N

N

N 个整数需要

31

N

31N

31N 个节点，算上最后的根节点一共有

31

N

+

1

31N+1

31N+1 个，而

N

=

1

0

5

N=10^5

N=105，保险起见，我们可以令第一维的大小为

31

⋅

1

0

5

+

10

=

3100010

31\cdot 10^5+10=3100010

31⋅105+10=3100010，从而可知Trie的初始化应当如下

const int M = 3100010;

int son[M][2], idx;

接下来是本题的重点，即如何寻找最大的异或对？传统的暴力解法是枚举每一个

a

[

i

]

a[i]

a[i]，然后再枚举每一个

a

[

j

]

a[j]

a[j]，计算

a

[

i

]

⊕

a

[

j

]

a[i]\oplus a[j]

a[i]⊕a[j] 并更新最大值。但这样做无疑是

O

(

n

2

)

O(n^2)

O(n2)，而我们又无法避开枚举

a

[

i

]

a[i]

a[i]，因此只能从「枚举

a

[

j

]

a[j]

a[j]」着手优化。

在暴力解法中，「枚举

a

[

j

]

a[j]

a[j]」的时间复杂度为

O

(

n

)

O(n)

O(n)，要想通过本题，我们必须将其降低至

O

(

log

⁡

n

)

O(\log n)

O(logn) 甚至更低，为此考虑用Trie来存储这些整数。固定

a

[

i

]

a[i]

a[i]，什么样的

a

[

j

]

a[j]

a[j] 才能使

a

[

i

]

⊕

a

[

j

]

a[i]\oplus a[j]

a[i]⊕a[j] 最大呢？显然当

a

[

j

]

a[j]

a[j] 的每一位与

a

[

i

]

a[i]

a[i] 都不相同时，

a

[

i

]

⊕

a

[

j

]

a[i]\oplus a[j]

a[i]⊕a[j] 达到最大值。但这样的

a

[

j

]

a[j]

a[j] 不一定存在于Trie中，因此我们从

a

[

i

]

a[i]

a[i] 的最高位开始，寻找Trie中是否有数字与

a

[

i

]

a[i]

a[i] 的最高位不同，如果有，则沿着相应路径继续搜索，否则，也必须沿着错误的路径进行搜索。

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

本题AC代码：

#include 
#include 

using namespace std;

const int M = 3100010, N = 100010;

int a[N], son[M][2], idx;

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

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

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, search(a[i]));
    cout << res << endl;

    return 0;
}

References

[1] https://oi-wiki.org/string/trie/

[2] https://www.acwing.com/activity/content/punch_the_clock/11/

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/1dc2337825.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐