字典树（Trie/前缀树）

目录

字典树的概念

字典树的逻辑

字典树的实现

易混点剖析

代码示例

---

字典树的概念

字典树（Trie）是一种空间换时间的数据结构，是一棵关于“字典”的树。主要用于统计、排序和保存大量的字符串。字典树是通过利用字符串的公共前缀来节约存储空间，因此字典树又叫前缀树。字典树是对于字典的一种存储方式。这个词典中的每个“单词”就是从根节点出发一直到某一个目标节点的路径，路径中每条边的字母连起来就是一个单词。

字典树的逻辑

在学习字典树之前我们先来看这样一个问题：

给你n个单词，并进行x次查找，每次查找随机一个单词word。

问：word是否出现在这n个单词中？

想想看，这像不像平常我们查字典？比如要在字典中查找单词“abandon”，我们一般是找到首字母为'a'的部分，然后再找第二个单词为‘b’的部分······如果字典中存在这个单词，那么我们最后就可以找到这个单词，反之则不能。

接下来，我们通过图解存储了单词{“a”,"abc",“bac”,“bbc”,"ca" }的字典树对上方内容进行解释：

从这张图我们可以看出，这棵字典树的每条边上都有一个字母（可以类比查字典时查找的第k个字母来理解），并且这棵树的一些节点被指定成了标记节点，用于表示到此为止是一个完整的单词。

字典树的实现

通过上面的图不难发现，字典树并不是二叉树，所以字典树的结构定义和二叉树的并不同，这里不要惯性思维了。通常我们定义多叉树时常用孩子表示法，像这样

struct TreeNode {
    ELEMENT_TYPE value;    //结点值
    TreeNode* children[NUM];    //孩子结点
};

字典树也类似：

struct TrieNode {
    int isEnd; //该结点是否是一个串的结束
    TrieNode* children[SIZE]; //字母映射表
};

常规的多叉树类型一般是，一个成员存放当前节点的内容，如上方的value成员；一个成员存放所有孩子节点的地址，如上方的children[NUM]成员，其数组中存放的是一个个TreeNode*类型的孩子节点的地址。

而字典树却与其有些不同，字典树的一个成员存放的是boo/intl型的isEnd成员，用于判断当前节点是否为一个单词的结束，如果是就标记为true，这样做的目的是在查找的时候方便确定找到最后是不是一个单词，因为并不是一个单词中所有的子串都是一个单词，例如”abandon“是一个单词，而其子串“ab“就不是一个单词。其另一个成员存放的也是一个指向孩子节点的指针，与常规的多叉树理解类似。

这里也许你会发现一些”端倪“：字典树的结构里好像并没有用于存储节点内容的成员，比如常规多叉树中的value成员。其实就是没有，但这并不妨碍我们实现这个功能，例如我们暂定字典中只有小写的26个字母，那么字典树的children[SIZE] 成员中SIZE就可以设置为26，那么我们就可以存储，那么我们将要查找或是存储的单词每一个字母（的ASCII值）减去一个'a' （字符a），那么其对应的值，就是我们要存放的children数组下标。了解过哈希表（散列表）的同学肯定会有一种茅塞顿开的感觉，因为这里其实就是用的哈希表的思路。下标为k的元素如果不为空（数组中的每一个元素都是一个指针）就说明这个元素有孩子节点，进而说明这个元素对应的字母是存在的。其中，一般第n层的children数组的下标k位置如果不为空，就表示这个单词中的第n个位置存在k下标位置所对应的字母。例如包含单词 "sea","sells","she" 的字典树图解如下：

---

在这里，我们还可以试着讨论一下为什么这个children成员用数组实现。（这一小部分内容与字典树的核心内容并没有多大关系，如果没有兴趣可以直接跳过）

相信有部分人（比如我）第一次接触字典树时对于

TrieNode* children[SIZE]

这种的定义是很难认同的，因为我们可能会觉得这会浪费很多空间，为什么不用链表等其它顺序结构来实现呢？

        首先，如果将数组替换为链表或其它线性结构，那么实现起来会非常繁琐，而且即使实现了，每次查找字母时都要进行一次链表的遍历，相较于数组的直接下标访问，是一个很费时的过程。

        其次，这里的数组其实就是一个哈希表，哈希表的一大优点就是用空间换时间，而且一个良好的哈希表结构是必须要留有一定的空闲位置的，所以这种实现方式也并非不妥。

        也许会有人想到用C++中的map/unordered_map来实现，这确实是可行的。首先，如果用map容器替换数组的话，实现起来并不是很难，理论上相较于哈希表确实会节省空间，但map的底层实现是红黑树，用一个红黑树去实现一个字典树，是不是有点小题大做了呢？其次，对于unordered_map来说，其本身就是一个哈希容器，与使用数组的本质是一样的，所以当然可行啦。

易混点剖析

       1、 字典树的实现是一种哈希表和树的结合。字典树的每次插入和查找操作的时间复杂度都是O(NlogN)的，而且为了防止删除操作对树操作不可逆的损坏，所以我们一般都是在结构体中额外增加一个成员，用以表示当前节点是否被删除（专业术语叫“惰性删除”）。

        2、不要将当前字母和当前节点弄混淆了。字典树的每一个节点都是一个“字母表”，并不是代指哪一个具体的字母。同时这也是字典树的特点：像字典一样，每次遍历到字符 ch 时，当前字典树节点不是直接代表这个 ch 的，而是表示当前节点的下一个字母是ch。不过，我们可以将其子节点看作代表一个固定的字符，如果是这样，那么字典树的根节点不代表任何字符。所以如果word字符串和trieTree（字典树）同时遍历的话，那么当前节点就表示在“字典”中，当前字符是否存在，而真正代表这个字符的是当前节点对应的一个字节点（next）。

       3、 字典树的增加操作很好解决，但删除和析构的维护成本就比较大了。因为C/C++不想java那样是完全封装好的，需要自己手动释放掉被删除的节点，而字典树的节点又异常的庞大（一般至少有26个next指针），所以字典树的释放就极大的增加了字典树的维护难度。

代码示例

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
 
class trieTree
{
private:
	int passBy;
	bool isEnd;
	trieTree* nexts[26];
public:
	//构造函数
	trieTree() :passBy(0), isEnd(0), nexts() {}
	//插入单词
	void insert(string word);
	//查找单词是否存在
	bool contains(string word);
	//查找前缀数量
	int pre_size(string pre);
	//删除单词
	void erase(string word);
};
void test1()
{
	trieTree* my_trie = new trieTree();
	my_trie->insert("apple");
	my_trie->insert("apple");
	my_trie->insert("banana");
	my_trie->insert("orange");
	my_trie->insert("applogise");
	my_trie->insert("app");
 
	my_trie->erase("applogise");
 
	cout << my_trie->contains("apple") << endl;
	cout << my_trie->contains("appl") << endl;
	cout << my_trie->contains("banana") << endl;
	cout << my_trie->contains("pear") << endl;
 
	cout << my_trie->pre_size("") << endl;
	cout << my_trie->pre_size("app") << endl;
	cout << my_trie->pre_size("appl") << endl;
	cout << my_trie->pre_size("ore") << endl;
}
class trieTree_byHash
{
private:
	int pass;
	bool end;
	unordered_map<char, trieTree_byHash*> nexts;
public:
	trieTree_byHash() :pass(0), end(0), nexts() {}
	//插入单词
	void insert(string word);
	//查找单词是否存在
	bool contains(string word);
	//查找前缀数量
	int pre_size(string pre);
	//删除单词
	void erase(string word);
};
void test2()
{
	trieTree_byHash* my_trie = new trieTree_byHash();
	my_trie->insert("apple");
	my_trie->insert("apple");
	my_trie->insert("banana");
	my_trie->insert("orange");
	my_trie->insert("applogise");
	my_trie->insert("app");
 
	my_trie->erase("applogise");
 
	cout << my_trie->contains("app") << endl;
	cout << my_trie->contains("appl") << endl;
	cout << my_trie->contains("banana") << endl;
	cout << my_trie->contains("pear") << endl;
 
	cout << my_trie->pre_size("") << endl;
	cout << my_trie->pre_size("app") << endl;
	cout << my_trie->pre_size("appl") << endl;
	cout << my_trie->pre_size("ore") << endl;
 
}
 
int main()
{
	test1();
	cout << endl;
	test2();
	return 0;
}
 
/*固定数组实现前缀树*/
//插入单词
void trieTree::insert(string word)
{
	//不重复插入单词
	if (this->contains(word))
		return;
	this->passBy++;
	trieTree* cur = this;
	for (char ch : word)
	{
		if (cur->nexts[ch - 'a'] == nullptr)
			cur->nexts[ch - 'a'] = new trieTree();
		cur = cur->nexts[ch - 'a'];
		cur->passBy++;
	}
	cur->isEnd = true;
}
//查找单词是否存在
bool trieTree::contains(string word)
{
	trieTree* cur = this;
	for (char ch : word)
	{
		if (cur->nexts[ch - 'a'] == nullptr)
			return false;
		cur = cur->nexts[ch - 'a'];
	}
	return cur->isEnd;
}
//查找前缀数量
int trieTree::pre_size(string pre)
{
	trieTree* cur = this;
	for (char ch : pre)
	{
		if (cur->nexts[ch - 'a'] == nullptr)
			return 0;
		cur = cur->nexts[ch - 'a'];
	}
	return cur->passBy;
}
//删除单词
void trieTree::erase(string word)
{
	if (!this->contains(word))
		return;
	trieTree* cur = this;
	cur->passBy--;
	int index = 0;
	while (--cur->nexts[word[index] - 'a']->passBy != 0)
	{
		cur = cur->nexts[word[index++] - 'a'];
	}
	//由于不会出现一样的单词，所以最后至少有一个节点的passBy为1
	//接着从index位置开始，将后面的节点全部delete
	trieTree* next = cur->nexts[word[index] - 'a'];
	cur->nexts[word[index] - 'a'] = nullptr;
	cur = next;
 
	while (cur != nullptr)
	{
		next = index + 1 < word.size() ? cur->nexts[word[++index] - 'a'] : nullptr;
		delete cur;
		cur = next;
	}
}
 
/*哈希表实现前缀树*/
//插入单词
void trieTree_byHash::insert(string word)
{
	if (this->contains(word))
		return;
	this->pass++;
	trieTree_byHash* cur = this;
	for (char ch : word)
	{
		if (cur->nexts.find(ch) == cur->nexts.end())
			cur->nexts[ch] = new trieTree_byHash();
		cur = cur->nexts[ch];
		cur->pass++;
	}
	cur->end = true;
}
//查找单词是否存在
bool trieTree_byHash::contains(string word)
{
	trieTree_byHash* cur = this;
	for (char ch : word)
	{
		if (cur->nexts.find(ch) == cur->nexts.end())
			return false;
		cur = cur->nexts[ch];
	}
	return cur->end;
}
//查找前缀数量
int trieTree_byHash::pre_size(string pre)
{
	trieTree_byHash* cur = this;
	for (char ch : pre)
	{
		if (cur->nexts.find(ch) == cur->nexts.end())
			return 0;
		cur = cur->nexts[ch];
	}
	return cur->pass;
}
//删除单词
void trieTree_byHash::erase(string word)
{
	if (!this->contains(word) && this->pass == 0)
		return;
	trieTree_byHash* cur = this;
	cur->pass--;
	int index = 0;
	while (index < word.size() && --cur->nexts[word[index]]->pass != 0)
	{
		cur = cur->nexts[word[index++]];
	}
	trieTree_byHash* next = cur->nexts[word[index]];
	cur->nexts[word[index]] = nullptr;
	cur = cur->nexts[word[index]];
	while (cur != nullptr)
	{
		next = index + 1 < word.size() ? cur->nexts[word[++index]] : nullptr;
		delete cur;
		cur = next;
	}
}