字典树的定义和代码模版

字典树的定义和使用场景

  • 定义

每个样本,从头结点开始,根据字符或者前缀数字构建出来的树,称之为前缀树

字典树

  • 使用场景

当需要根据前缀信息查询时,可以使用字典树

字典树的实现

用类描述

最经典的描述,但是对于字符种类过多的情况,难以处理

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
#include <iostream>

using namespace std;

typedef struct TREENODE {
int pass;
int end;
struct TREENODE* next[26] = {};
TREENODE() : pass(0), end(0) {};
}TreeNode;

class Trie {
public:
TreeNode* root = nullptr;
Trie() {
root = new TreeNode();
}
// 插入word
void insert(string word) {
TreeNode* node = root;
node->pass++;
for (auto c : word) {
int path = c - 'a';
// 如果路径为空 则添加路径
if (!node->next[path]) {
node->next[path] = new TreeNode();
}
node = node->next[path];
node->pass++;
}
node->end++;
}
// 查询word个数
int countWord(string word) {
TreeNode* node = root;
for (auto c : word) {
int path = c - 'a';
// 如果路径为空 则说明不存在这个word
if (!node->next[path]) return 0;
node = node->next[path];
}
return node->end;
}
// 查询前缀
int countPrefix(string prefix) {
TreeNode* node = root;
for (auto c : prefix) {
int path = c - 'a';
// 如果路径为空 则说明不存在这个prefix
if (!node->next[path]) return 0;
node = node->next[path];
}
return node->pass;
}
// 删除word
void erase(string word) {
// 先判断是否存在这个word
if (countWord(word) > 0) {
TreeNode* node = root;
node->pass--;
for (auto c : word) {
int path = c - 'a';
if (--node->next[path]->pass == 0) {
// delete 后面的节点
node->next[path] = nullptr;
return;
}
node = node->next[path];
}
node->end--;
}
}
};

哈希表+类 实现

使用哈希表进行了优化,可以处理字符种类多的情况,但是依旧浪费大量的空间

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
typedef struct TREENODE {
int pass;
int end;
unordered_map<char, struct TREENODE*> next;
TREENODE() : pass(0), end(0) {};
}TreeNode;

class Trie {
public:
TreeNode* root = nullptr;
Trie() {
root = new TreeNode();
}
// 插入word
void insert(string word) {
TreeNode* node = root;
node->pass++;
for (auto c : word) {
// 如果c不存在路径中 则新建一条路径
if (node->next.count(c) == 0) {
node->next[c] = new TreeNode();
}
node = node->next[c];
node->pass++;
}
node->end++;
}
// 查询word个数
int countWord(string word) {
TreeNode* node = root;
for (auto c : word) {
if (node->next.count(c) == 0) return 0;
node = node->next[c];
}
return node->end;
}
// 查询前缀
int countPrefix(string word) {
TreeNode* node = root;
for (auto c : word) {
if (node->next.count(c) == 0) return 0;
node = node->next[c];
}
return node->pass;
}
// 删除word
void erase(string word) {
if (countWord(word) > 0) {
TreeNode* node = root;
node->pass--;
for (auto c : word) {
if (--node->next[c]->pass == 0) {
// delete 节点
node->next.erase(c);
return;
}
node = node->next[c];
}
node->end--;
}
}
};

用静态数组实现

使用静态数组对空间进行了优化,这样无论是多大数据,都可以只申请一次确定空间,进行查询

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
#include <iostream>

using namespace std;

#define MAX 1000

class Trie {
public:
int nexts[MAX][26] = { {0} };
int pass[MAX] = { 0 };
int end[MAX] = { 0 };
int cnt = 1;
Trie() {
cnt = 1;
}
// 插入word
void insert(string word) {
int cur = 1;
pass[cur]++;
for (auto c : word) {
// 如果c不存在路径中 则新建一条路径
int path = c - 'a';
if (nexts[cur][path] == 0) {
nexts[cur][path] = ++cnt;
}
cur = nexts[cur][path];
pass[cur]++;
}
end[cur]++;
}
// 查询word个数
int countWord(string word) {
int cur = 1;
for (auto c : word) {
int path = c - 'a';
if (nexts[cur][path] == 0) return 0;
cur = nexts[cur][path];
}
return end[cur];
}
// 查询前缀
int countPrefix(string word) {
int cur = 1;
for (auto c : word) {
int path = c - 'a';
if (nexts[cur][path] == 0) return 0;
cur = nexts[cur][path];
}
return pass[cur];
}
// 删除word
void erase(string word) {
if (countWord(word) > 0) {
int cur = 1;
pass[cur]--;
for (auto c : word) {
int path = c - 'a';
if (--pass[nexts[cur][path]] == 0) {
nexts[cur][path] = 0;
return;
}
cur = nexts[cur][path];
}
end[cur]--;
}
}

};