Trie树

发表于

Trie(字典树)可以保存一些字符串->值得对应关系，其实它和hashmap的功能相同，以key-value映射的方式用空间换时间。（只不过Trie的key往往就是字符串）

Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ，其中 k 为 key（也就是字符串的size） 的长度，与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的，但在计算 hash 的时候就肯定会是 O(k) ，而且还有碰撞之类的问题；Trie 的缺点是空间消耗很高。

Trie树有一些特性：
1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3）每个节点的所有子节点包含的字符都不相同。
4）如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
5）插入查找的复杂度为O(n)，n为字符串长度。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
struct Trie_node
{
	bool exist;
	Trie_node* next[26];
	int count;
};
Trie_node* createTrie()
{
	Trie_node* root = new Trie_node();
	root->count = 0;
	root->exist = false;
	memset(root->next, 0, sizeof(root->next));
	return root;
}
void deleteTrie(Trie_node* root)
{
	for (int i = 0; i < 26; ++i)
	{
		if (root->next[i] != NULL)
			deleteTrie(root->next[i]);
	}
	delete root;
}
void insert(Trie_node* root, string word)
{
	int nb = word.size();
	if (nb == 0) return;
	Trie_node* pt = root;
	root->count++;
	for (int i = 0; i < nb; ++i)
	{
		int p = word[i] - 'a';
		if (pt->next[p] == NULL)
		{
			Trie_node* tt = new Trie_node();
			tt->count = 1;
			memset(tt, NULL, sizeof(tt->next));
			if (i == nb - 1)
				tt->exist = true;
			else
				tt->exist = false;
			pt->next[p] = tt;
		}
		else
		{
			pt->next[p]->count++;
			if (i == nb - 1)
				pt->next[p]->exist = true;
		}
		pt = pt->next[p];
	}
	return;
}
int find(Trie_node* root, string word)
{
	int nb = word.size();
	if (nb == 0) return 0;
	Trie_node* pt = root;
	for (int i = 0; i < word.size(); ++i)
	{
		int p = word[i] - 'a';
		if (pt->next[p] == NULL) return 0;
		if (i == nb - 1) return pt->next[p]->count;
		else
			pt = pt->next[p];
	}
}
int Trie_main()
{
	int N, M;
	vector<string> words;
	vector<string> searches;
	scanf("%d", &N);
	getchar();
	for (int i = 0; i < N; ++i)
	{
		string temp;
		getline(cin, temp);
		words.push_back(temp);
	}
	scanf("%d", &M);
	getchar();
	for (int i = 0; i < M; ++i)
	{
		string temp;
		getline(cin, temp);
		searches.push_back(temp);
	}
	Trie_node* root = createTrie();
	for (int i = 0; i < words.size(); ++i)
	{
		insert(root, words[i]);
	}
	for (int i = 0; i < searches.size(); ++i)
	{
		printf("%d\n", find(root, searches[i]));
	}
	deleteTrie(root);
	return 0;
}