Implement Trie (Prefix Tree) - 实现 Trie (前缀树 - 字典树)

待我称王封你为后i 2022-10-19 00:56 209阅读 0赞

# **Implement Trie (Prefix Tree) - 实现 Trie (前缀树 - 字典树)** #

[https://leetcode-cn.com/problems/implement-trie-prefix-tree/][https_leetcode-cn.com_problems_implement-trie-prefix-tree]

A Trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.  
Trie (前缀树/字典树) 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。它是一种特殊的多叉树，它的 TrieNode 中 chidren 是一个大小为 26 的一维数组，分别对应了 26 个英文字符 ‘a’ ~ ‘z’，形成了一棵 26 叉树。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

核心是使用边来代表有无字符，使用点来记录是否为单词结尾。利用字符串的公共前缀来节约存储空间 Trie 树主要是利用词的公共前缀缩小查词范围、通过状态间的映射关系避免了字符的遍历，从而达到高效检索的目的。

*  根节点不保存任何信息，根节点不包含字符，除根节点外每一个节点都只包含一个字符。
 *  关键词放到前缀树时，需要把它拆成各个字符，每个字符按照其在 ‘a’ ~ ‘z’ 的序号，放在对应的 chidren 里面。下一个字符是当前字符的子节点。从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
 *  一个输入字符串构建前缀树结束的时候，需要把该节点的 isend 标记为 true，说明从根节点到当前节点的路径，构成了一个关键词。每个节点的所有子节点包含的字符都不相同。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]

该前缀树中拥有的字符串分别为：\[“am”, “bad”, “be”, “so”\]，若两个字符串有同样的前缀，在插入时，就会省去了相同部分插入的步骤，直接从不相同的第一个字符开始插入即可。

Trie 前缀树，就是一个树，第一个枝干上有 26 个分支，代表 26 个字母，每个字母的分支上同样有 26 个分支，顺着枝干往下就能够拼成一个单词。

Implement the Trie class:

*  `Trie()` Initializes the trie object.  
    初始化字典树对象。
 *  `void insert(String word)` Inserts the string word into the trie.  
    向字典树中插入字符串 word。
 *  `boolean search(String word)` Returns `true` if the string word is in the trie (i.e., was inserted before), and `false` otherwise.  
    如果字符串 word 在前缀树中，返回 `true` (在检索之前已经插入)；否则，返回 `false`。
 *  `boolean startsWith(String prefix)` Returns `true` if there is a previously inserted string word that has the prefix prefix, and `false` otherwise.  
    如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 `true`；否则，返回 `false`。

### Trie - Prefix tree ###

Trie (\[traɪ\])：字典树，单词查找树  
Prefix tree (\['priːfɪks\])：前缀树

A `trie`, or `prefix tree`, is a tree data structure for storing strings (keywords) in sorted order.  
`trie` or `prefix tree` 是一种树数据结构，用于按照排序顺序存储字符串 (关键字)。

Trie 树是一个有根的树，其结点有以下字段：

*  最多 MAX\_NUM 个指向子结点的链接，其中每个链接对应字母表数据集中的一个字母。假定 MAX\_NUM 为 26，小写拉丁字母的数量。指向子节点的指针数组 `struct TRIE *children[ALPHABET]; // [] > *`。数组长度为 26，即小写英文字母的数量。此时 `children[0]` 对应小写字母 `a`，`children[1]` 对应小写字母 `b`，…，`children[25]` 对应小写字母 `z`。
 *  布尔字段，以指示该节点是否为字符串的结尾。

### 插入字符串 ###

从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：

*  子节点存在。沿着指针移动到子节点，继续处理下一个字符。
 *  子节点不存在。创建一个新的子节点，记录在children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。  
    重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。

### 查找前缀 ###

从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：

*  子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
 *  子节点不存在。说明字典树中不包含该前缀，返回空指针。  
    重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。

若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 isend 为真，则说明字典树中存在该字符串。

时间复杂度：初始化为 O(1)，其余操作为 O(|S|)，其中 |S| 是每次插入或查询的字符串的长度。  
使用前缀树 (Trie) 的数据结构使得插入、查询全词、查询前缀的时间复杂度与已插入的单词数目无关，这是前缀树 (Trie) 解法优于有序集合解法的关键。

*  Trie 的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie 的形状都是唯一的。
 *  查找或插入一个长度为  L L L 的单词，访问 next 数组的次数最多为  L + 1 L+1 L\+1，和 Trie 中包含多少个单词无关。
 *  Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为  n n n，字母表的大小为  m m m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为  O ( m n ) O(m^n) O(mn)。

**Example 1:**

Input:
    ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] - 函数名
    [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] - 函数参数
    
    Output:
    [null, null, true, false, true, null, true]
    
    Explanation:
    Trie trie = new Trie();
    trie.insert("apple");
    trie.search("apple");   // return True
    trie.search("app");     // return False
    trie.startsWith("app"); // return True
    trie.insert("app");
    trie.search("app");     // return True

Constraints:

*  1 <= word.length, prefix.length <= 2000.
 *  word and prefix consist only of `lowercase` English letters.
 *  At most  3 ∗ 1 0 4 3 \* 10^4 3∗104 calls in total will be made to insert, search, and startsWith.

1.  极端情况下，`trie.insert()` 调用  3 ∗ 1 0 4 3 \* 10^4 3∗104 次，同时 `1 <= word.length <= 2000`，则字典树节点数最大可达  2000 ∗ 3 ∗ 1 0 4 2000 \* 3 \* 10^4 2000∗3∗104。

## 1. solution 1 ##

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2020 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #define ALPHABET (26)
    #define MAX_NODE_NUM (2000 * 30000 + 4)
    
    typedef struct TRIE {
    	struct TRIE *parent;
    	struct TRIE *children[ALPHABET];  // [] > *
    	int children_num;
    	int isend;  // default = 0
    	char ch;
    } Trie;
    
    // Trie node_pool[MAX_NODE_NUM];
    // int node_pool_idx = 0;  // init()
    // Trie root_node;  // init()
    
    Trie* init_trie(Trie *parent, const char ch)
    {
    	Trie *node = (Trie *)malloc(1 * sizeof(Trie));
    	node->parent = parent;
    	node->children_num = 0;
    	node->isend = 0;  // default = 0
    	node->ch = ch;
    
    	for (int i = 0; i < ALPHABET; ++i) {
    		(node->children)[i] = NULL;
    	}
    
    	return node;
    }
    
    /** Initialize your data structure here. */
    Trie* trieCreate() {
    	Trie *root_head = init_trie(NULL, 0);
    
    	return root_head;
    }
    
    /** Inserts a word into the trie. */
    void trieInsert(Trie *obj, char *word) {
    	// 1 <= word.length, prefix.length <= 2000
    	if ((NULL == obj) || (NULL == word)) {
    		return;
    	}
    
    	Trie *ptr_node = obj;
    	int i = 0;
    	while (word[i] != '\0')
    	{
    		const char ch = word[i];
    		const int idx = ch - 'a';
    		if (NULL == (ptr_node->children)[idx])
    		{
    			Trie *node = init_trie(ptr_node, ch);
    
    			(ptr_node->children)[idx] = node;
    			ptr_node->children_num += 1;
    		}
    
    		ptr_node = (ptr_node->children)[idx];
    
    		++i;
    	}
    
    	ptr_node->isend = 1;
    }
    
    /** Returns if the word is in the trie. */
    bool trieSearch(Trie *obj, char *word) {
    	// 1 <= word.length, prefix.length <= 2000
    	if ((NULL == obj) || (NULL == word)) {
    		return false;
    	}
    
    	Trie *ptr_node = obj;
    	int i = 0;
    	while (word[i] != '\0')
    	{
    		const char ch = word[i];
    		const int idx = ch - 'a';
    		if (NULL == (ptr_node->children)[idx]) {
    			return false;
    		}
    
    		ptr_node = (ptr_node->children)[idx];
    
    		++i;
    	}
    
    	if (1 == ptr_node->isend) {
    		return true;
    	}
    	else {
    		return false;
    	}
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool trieStartsWith(Trie *obj, char *prefix) {
    	// 1 <= word.length, prefix.length <= 2000
    	if ((NULL == obj) || (NULL == prefix)) {
    		return false;
    	}
    
    	Trie *ptr_node = obj;
    	int i = 0;
    	while (prefix[i] != '\0')
    	{
    		const char ch = prefix[i];
    		const int idx = ch - 'a';
    		if (NULL == (ptr_node->children)[idx]) {
    			return false;
    		}
    
    		ptr_node = (ptr_node->children)[idx];
    
    		++i;
    	}
    
    	return true;
    }
    
    void def_trie_v1(Trie *node)
    {
    	for (int i = 0; i < ALPHABET; ++i)
    	{
    		if (NULL != (node->children)[i])
    		{
    			def_trie_v1((node->children)[i]);
    		}
    	}
    
    	free(node);
    	return;
    }
    
    void def_trie_v2(Trie *node)
    {
    	if (0 == node->children_num)
    	{
    		free(node);
    		return;
    	}
    
    	for (int i = 0; i < ALPHABET; ++i)
    	{
    		if (NULL != (node->children)[i])
    		{
    			def_trie_v2((node->children)[i]);
    		}
    	}
    
    	free(node);
    	return;
    }
    
    void def_trie_v3(Trie *node)
    {
    	if (0 == node->children_num)
    	{
    		free(node);
    		return;
    	}
    
    	int children_num = node->children_num;
    	for (int i = 0; i < ALPHABET; ++i)
    	{
    		if (NULL != (node->children)[i])
    		{
    			def_trie_v3((node->children)[i]);
    			--children_num;
    		}
    
    		if (children_num <= 0) {
    			break;
    		}
    	}
    
    	free(node);
    	return;
    }
    
    void trieFree(Trie *obj) {
    	if (NULL == obj) {
    		return;
    	}
    
    	// def_trie_v1(obj);
    	// def_trie_v2(obj);
        def_trie_v3(obj);
    }
    
    /**
    * Your Trie struct will be instantiated and called as such:
    * Trie *obj = trieCreate();
    * trieInsert(obj, word);
    
    * bool param_2 = trieSearch(obj, word);
    
    * bool param_3 = trieStartsWith(obj, prefix);
    
    * trieFree(obj);
    */

![在这里插入图片描述][20210711140709367.png_pic_center]

## 2. solution 2 ##

将需要释放内存的 Trie 节点全部挂载到一个双向链表上，通过访问链表逐个删除节点，释放内存。这样避免通过 DFS 删除节点。

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2020 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #define ALPHABET (26)
    #define MAX_NODE_NUM (2000 * 30000 + 4)
    
    typedef struct TRIE {
    	struct TRIE *prev;
    	struct TRIE *next;
    	struct TRIE *parent;
    	struct TRIE *children[ALPHABET];  // [] > *
    	int children_num;
    	int isend;  // default = 0
    	char ch;
    } Trie;
    
    // Trie node_pool[MAX_NODE_NUM];
    // int node_pool_idx = 0;  // init()
    Trie root_node;  // init()
    Trie *array_head = &root_node;
    
    void insert_node(Trie *head, Trie *node)
    {
    	node->next = head->next;
    	node->prev = head;
    	node->next->prev = node;
    	head->next = node;
    }
    
    void delete_node_src(Trie *node)
    {
    	Trie *prev_node = node->prev;
    	Trie *next_node = node->next;
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    void delete_node(Trie *node)
    {
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    Trie* init_trie(Trie *parent, const char ch)
    {
    	Trie *node = (Trie *)malloc(1 * sizeof(Trie));
    	node->parent = parent;
    	node->children_num = 0;
    	node->isend = 0;  // default = 0
    	node->ch = ch;
    
    	for (int i = 0; i < ALPHABET; ++i) {
    		(node->children)[i] = NULL;
    	}
    
    	return node;
    }
    
    /** Initialize your data structure here. */
    Trie* trieCreate() {
    	Trie *root_head = init_trie(NULL, 0);
    
    	array_head->prev = array_head->next = array_head;
    
    	insert_node(array_head, root_head);
    
    	return root_head;
    }
    
    /** Inserts a word into the trie. */
    void trieInsert(Trie *obj, char *word) {
    	// 1 <= word.length, prefix.length <= 2000
    	if ((NULL == obj) || (NULL == word)) {
    		return;
    	}
    
    	Trie *ptr_node = obj;
    	int i = 0;
    	while (word[i] != '\0')
    	{
    		const char ch = word[i];
    		const int idx = ch - 'a';
    		if (NULL == (ptr_node->children)[idx])
    		{
    			Trie *node = init_trie(ptr_node, ch);
    
    			(ptr_node->children)[idx] = node;
    			ptr_node->children_num += 1;
    
    			insert_node(array_head, node);
    		}
    
    		ptr_node = (ptr_node->children)[idx];
    
    		++i;
    	}
    
    	ptr_node->isend = 1;
    }
    
    /** Returns if the word is in the trie. */
    bool trieSearch(Trie *obj, char *word) {
    	// 1 <= word.length, prefix.length <= 2000
    	if ((NULL == obj) || (NULL == word)) {
    		return false;
    	}
    
    	Trie *ptr_node = obj;
    	int i = 0;
    	while (word[i] != '\0')
    	{
    		const char ch = word[i];
    		const int idx = ch - 'a';
    		if (NULL == (ptr_node->children)[idx]) {
    			return false;
    		}
    
    		ptr_node = (ptr_node->children)[idx];
    
    		++i;
    	}
    
    	if (1 == ptr_node->isend) {
    		return true;
    	}
    	else {
    		return false;
    	}
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool trieStartsWith(Trie *obj, char *prefix) {
    	// 1 <= word.length, prefix.length <= 2000
    	if ((NULL == obj) || (NULL == prefix)) {
    		return false;
    	}
    
    	Trie *ptr_node = obj;
    	int i = 0;
    	while (prefix[i] != '\0')
    	{
    		const char ch = prefix[i];
    		const int idx = ch - 'a';
    		if (NULL == (ptr_node->children)[idx]) {
    			return false;
    		}
    
    		ptr_node = (ptr_node->children)[idx];
    
    		++i;
    	}
    
    	return true;
    }
    
    void def_trie_v1(Trie *node)
    {
    	for (int i = 0; i < ALPHABET; ++i)
    	{
    		if (NULL != (node->children)[i])
    		{
    			def_trie_v1((node->children)[i]);
    		}
    	}
    
    	free(node);
    	return;
    }
    
    void def_trie_v2(Trie *node)
    {
    	if (0 == node->children_num)
    	{
    		free(node);
    		return;
    	}
    
    	for (int i = 0; i < ALPHABET; ++i)
    	{
    		if (NULL != (node->children)[i])
    		{
    			def_trie_v2((node->children)[i]);
    		}
    	}
    
    	free(node);
    	return;
    }
    
    void def_trie_v3(Trie *node)
    {
    	if (0 == node->children_num)
    	{
    		free(node);
    		return;
    	}
    
    	int children_num = node->children_num;
    	for (int i = 0; i < ALPHABET; ++i)
    	{
    		if (NULL != (node->children)[i])
    		{
    			def_trie_v3((node->children)[i]);
    			--children_num;
    		}
    
    		if (children_num <= 0) {
    			break;
    		}
    	}
    
    	free(node);
    	return;
    }
    
    void trieFree(Trie *obj) {
    	if (NULL == obj) {
    		return;
    	}
    
    	// def_trie_v1(obj);
    	// def_trie_v2(obj);
    	// def_trie_v3(obj);
    
    	Trie *ptr_node = array_head->next;
    	while (ptr_node != array_head)
    	{
    		Trie *tmp = ptr_node->next;
    
    		delete_node(ptr_node);
    		free(ptr_node);
    
    		ptr_node = tmp;
    	}
    }
    
    /**
    * Your Trie struct will be instantiated and called as such:
    * Trie *obj = trieCreate();
    * trieInsert(obj, word);
    
    * bool param_2 = trieSearch(obj, word);
    
    * bool param_3 = trieStartsWith(obj, prefix);
    
    * trieFree(obj);
    */

## References ##

[https://leetcode-cn.com/problems/implement-trie-prefix-tree/][https_leetcode-cn.com_problems_implement-trie-prefix-tree]

[https_leetcode-cn.com_problems_implement-trie-prefix-tree]: https://leetcode-cn.com/problems/implement-trie-prefix-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/ef5d04a2142942f6b6f243bae2747535.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/201c4083dd0c49da91b5a1b47ae84f58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221005/fe2fd939c12347b288fced4628c67758.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221005/69e16d25a7af4561862709b72dca8c6b.png
[20210711140709367.png_pic_center]: /images/20221005/0854f20e392c4f7fa55f5383276c7e8f.png