数据结构 : 前缀树 Trie_trie前缀树

前缀树 Trie

1 什么是Trie树

• Trie树,又叫字典树 前缀树 单词查找树 键树
• 是一种树形结构，是一种哈希树的变种
• 是一种多叉树.

1.1 基本性质:

1. 根节点不包含字符. 除了根节点之外,每个子节点包含一个字符.
2. 从根节点到某一节点,路径通过经过的字符连接.为该节点对应字符串
3. 每个节点的所有子节点包换的字符互不相同

通常,会在节点结构中设置一个标志,用来标记该结点处是否构成一个单词（关键字）.

2 Tire树的优缺点

Tire树的核心思想是通过 空间来换时间.

利用字符串的公共前缀来减少无谓的字符串比较

2.1 优点

1. 插入和查询效率高! 都是 O(m). m为字符串长度.

2. Tire树中不同的关键字不会产生冲突.

   Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生.

3. Trie树不用求 hash 值.对短字符串有更快的速度.

   通常求hash值也是需要遍历字符串的.

4. Trie树可以对关键字按字典序排序

2.2 缺点

1. 当 hash 函数很好时. Trie树的查找效率会低于哈希搜索

2. 空间消耗比较大

   优化:

   压缩字典树 Compressed Trie

   Ternay Search Trie 三分搜索树

3 Trie树的应用

3.1 字符串检索

检索/查询功能是Trie树最原始的功能

思路 是从根节点开始一个一个字符进行比较

• 如果沿路比较,发现不同的字符,则表示该字符串在集合中不存在
• 如果所有的字符全部比较完并且全部相同,还需要判断一下最后一个节点的标志位.标记该节点是否代表一个关键字.

class Node {
    public:
    bool isWord; // 标记是否是一个关键字
    map<char, Node*> next; // 存放各个子节点
    Node(bool isWord) {
        this->isWord = isWord;
    }
    Node() {
        Node(false);
    }
};
1
2
3
4
5
6
7
8
9
10
11

3.2 词频统计

Trie树常被搜索引擎系统用于文本词频统计

思路 就是增加一个 count 来计数. 对每一个关键字执行插入操作时,若已经存在,则计数+1.若不存在则,插入后 count 置为1.

3.3 字符串排序

Trie树可以对大量字符串按字典序进行排序

思路 就是遍历一遍所有的关键字,将他们全部插入 Trie 树.

树的每个结点的所有儿子,很显然按照字母表排序.然后先序遍历输出 Trie 树中所有关键字即可.

3.4 前缀匹配

例如: 找出一个字符串集合中所有以ab开头的字符串 . 需要用所有的字符串构造一个 trie 树. 然后然后输出 以 a->b-> 开头的路径的搜有关键字即可.

trie树前缀匹配常用于搜索提示 :

如当输入一个网址. 可以自动搜索出可能的选择.

当没有完全匹配的搜索结果,可以返回前缀最相似的可能.

3.5 作为其他数据结构和算法的辅助结构

后缀树 : (字符串模式识别)

4 C++实现简单的 Trie 树

class Trie {
private:
	class Node {
	public:
		bool isWord;

		map<char, Node*> next;
		Node(bool isWord) {
			this->isWord = isWord;
		}
		Node() {
			Node(false);
		}
	};
	
	Node* root; // 根节点
	int size;

public:
	Trie() {
		root = new Node();
		size = 0;
	}
	
	// 获得Trie存储的单词数量
	int getSize() {
		return size;
	}

	// trie中添加一个新的word
	void add(string word) {
		Node* cur = root;
		for (int i = 0; i < word.size(); i++) {
			char c = word[i]; // 当前的字符
			if(cur->next.count(c)==0){ // 如果找不到呢,就要自己加一个
				cur->next.insert(make_pair(c, new Node(false)));
			}
			// 移动节点到下一个节点
			cur = cur->next[c];
		}
		// 若当前这个单词满意出现过,则把它置为真
		if (!cur->isWord) {
			cur->isWord = true;
			size++;
		}
	}

	// 查询单词word是否在Trie中
	bool contains(string word) {
		Node* cur = root;
		for (int i = 0; i < word.size(); i++) {
			char c = word[i];
			if (cur->next.count(c) == 0) {
				return false;
			}
			cur = cur->next[c];
		}
		return cur->isWord;
	}

	// 在Trie中查找是否有单词以orefix为前缀
	bool isPrefix(string prefix) {
		Node* cur = root;
		for (int i = 0; i < prefix.size(); i++) {
			char c = prefix[i];
			if (cur->next.count(c) == 0) {
				return false;
			}
			cur = cur->next[c];
		}
		return true;
	}

};
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

5 Trie删除操作

待续

6 LeetCode题解

208. Implement Trie (Prefix Tree)

参考上面代码

211. Add and Search Word - Data structure design

class WordDictionary {
public:
	class Node {
	public:
		bool isWord;
		map<char, Node*> next;

		Node(bool isWord) {
			this->isWord = isWord;
		}

		Node() {
			Node(false);
		}
	};

	Node* root;

	/** Initialize your data structure here. */
	WordDictionary() {
		root = new Node(false);
	}

	/** Adds a word into the data structure. */
	void addWord(string word) {
		Node* cur = root;
		for (int i = 0; i < word.size(); i++) {
			char c = word[i]; // 当前的字符
			if (cur->next.count(c) == 0) { // 如果找不到呢,就要自己加一个
				cur->next.insert(make_pair(c, new Node(false)));
			}
			// 移动节点到下一个节点
			cur = cur->next[c];
		}
		// 若当前这个单词满意出现过,则把它置为真
		if (!cur->isWord) {
			cur->isWord = true;
		}
	}

	bool search(Node* node, string word, int start) {
		// 递归结束条件
		if (start == word.size()) {
			return node->isWord;
		}

		Node* cur = node;
		char c = word[start];
		if (c == '.') {
			for (auto it = cur->next.begin(); it != cur->next.end(); it++) {
				if (search(it->second,word,start+1))
				{
					return true;
				}
			}
			return false;
		}
		else { // 不是'.' 就要判断存不存在 c
			if (cur->next.count(c) == 0) {
				return false;
			}
			cur = cur->next[c];
			return search(cur, word, start + 1);
		}
	}

	/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
	bool search(string word) {
		Node* cur = root;
		return search(cur, word, 0);
	}
};
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

677

class MapSum {
public:

	class Node {
	public:
		Node(int val) {
			this->val = val;
		}
		Node() {
			Node(0);
		}
		map<char, Node*> next;
		int val;
	};

	Node* root;

	/** Initialize your data structure here. */
	MapSum() {
		root = new Node();
	}
	void insert(string key, int val) {
		Node* cur = root;
		for (auto c : key) {
			if (cur->next.count(c) == 0) {
				cur->next.insert(make_pair(c, new Node(0)));
			}
			cur = cur->next[c];
		}
		cur->val = val;
	}


	int sum(Node* node) {
		int res = 0;
		Node* cur = node;
		if (cur->val != 0) {
			res += cur->val;
		}
		for (auto it = cur->next.begin(); it != cur->next.end(); it++) {
			res += sum(it->second);
		}
		return res;
	}

	int sum(string prefix) {
		Node* cur = root;
		for (auto c : prefix) {
			if (cur->next.count(c) == 0) {
				return 0;
			}
			cur = cur->next[c];
		}
		// 找到了以prefix开头的节点,接下来要遍历所有的的节点
		return sum(cur);
	}
};

/**
* Your MapSum object will be instantiated and called as such:
* MapSum obj = new MapSum();
* obj.insert(key,val);
* int param_2 = obj.sum(prefix);
*/
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

472

212

421

参考文献

Trie树介绍

Trie数（前缀树/字典树）简介及Leetcode上关于前缀树的题