字典树（Trie）详解_trie树算法 通俗讲解

字典树 (Trie)，又称单词查找树、前缀树，是一种树形结构，是一种哈希树的变种。

在统计、排序和保存大量的字符串（但不仅限于字符串）是具有更小的时间复杂度，因此可以应用于统计、排序和保存大量的字符串，经常被搜索引擎系统用于文本词频统计。

它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

性质：

1. 根节点不包含字符，除根结点外的每一个节点都只包含一个字符
2. 从根节点到某一结点，将路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

结点

class TrieNode {
public:
	TrieNode() :child(26, nullptr), isEnd(false) {
 
	}
	vector<TrieNode*> child;
    //表示某个单词在以这个结点为结尾
	bool isEnd;
};

Trie树

class Trie {
public:
	Trie() {
		root = new TrieNode;
	}
 
	~Trie() {
		clearNode(root);
		root = nullptr;
	}
 
	void clearNode(TrieNode* root)
	{
		if (root == nullptr) return;
 
		for (int i = 0; i < 26; i++)
		{
			clearNode(root->child[i]);
		}
		delete root;
	}
 
	
private:
 
	TrieNode* root;
};

插入单词

如果要插入某个单词，遍历单词的每个字符，某个字符对应的节点为空的话，创建对应的节点，并继续从该节点出发，构建下一个字符对应的节点

void insert(string word) {
 
	TrieNode* cur = root;
	for (int i = 0; i < word.size(); i++)
	{
		if (cur->child[word[i] - 'a'] == nullptr)
		{
			cur->child[word[i] - 'a'] = new TrieNode;
		}
		cur = cur->child[word[i] - 'a'];
	}
	cur->isEnd = true;
}

查找单词

在字典树上遍历单词对应的节点，直到最后一个字符存在并且结束标志为true

bool search(string word) {
	TrieNode* cur = root;
	for (int i = 0; i < word.size(); i++)
	{
		if (cur->child[word[i] - 'a'] == nullptr)
		{
			return false;
		}
		cur = cur->child[word[i] - 'a'];
	}
	return cur->isEnd;
 
}

如果想要实现删除某个单词，则可在字典树上遍历单词对应的节点，直到最后一个字符存在并将结束标志为false

应用场景

字符串检索：(事先将已知的一些字特串(字典)的信息保存到Trie 树里,查找另外一些未知字符串是否出现过或者出现频率。

• 给出N个单词组成的熟词表,以及一篇全用小写英文书写的文章按最早出现的顺序写出在熟词表中的生词。
• 给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例:若rob是不良单词,那么文本 problem含有不良单词。
• 1000万个字符串,其中有些是重复的,需要把重复的全部去掉，保留没有重复的字符串。

排序：Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串，便是按字典树排序的结果。

字符串最长公共前缀：Trie树利用多个字符串的公共前缀来节省存储空间，当我们把大量字符串的存储到一棵Trie树上，可以快速得到字符串的公共前缀。

字符串搜索的前缀匹配：Trie常用于搜索提示，如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。Trie检索的时间复杂度可以做到O(n)，n是要检索的单词的长度。

缺点：字典树的内存消耗非常大。虽然不同单词共享前缀，但其实Trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针。