Trie（字典树）详解与C++实现

2023-12-01 22:27| 来源: 网络整理| 查看: 265

文章目录参考资料Trie Introduction（介绍字典树）C++实现Trie 应用

参考资料甜姨的力扣题解：https://zhuanlan.zhihu.com/p/120150816力扣官方题解：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/

1.2.资料都是基于Java来对Trie进行实现，3.是c++的实现，原理都介绍的非常棒！

Trie Introduction（介绍字典树）

Trie也叫字典树、前缀树、单词查找树等等，它常用来存储单词（和语种无关），相比于HashMap等操作，Trie能在存储多个具有相同前缀的键时，使用较少的空间。并且Tire树只需要O(M)的时间复杂度，其中M为键长。

下图演示了一个保存8个单词的字典树结构，8个单词分别是：“A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”。（蓝色节点表示单词的结尾字符）在这里插入图片描述【示例来自参考资料1】说明 root节点为Null；把从root节点出发到蓝色节点的路径上所表示的字符连接起来，就构成一个单词；从root节点出发，都是单词列表里某个单词/某些单词的前缀；如果某个字符串没有出现在这棵树的路径上，那说明其不是所给出单词列表的前缀。

然后相比一般的多叉树，Trie在节点的数据结构设计上也有很多不同。

class Trie{ private: bool flag; Trie* next[R]; };

其中val表示的是该节点是否为尾节点（是不是对应键的结尾），next[R]表示的是指向R个子节点的链接。比如我们现在要表示英语单词的话，R就为26。说明因为flag只用来表示该节点是否为一个单词的结尾，然后next[R]可以看做是指向26个字母的映射表，保存了对于当前节点而言，下一个可能出现的字符链接。所以，上面的图并不是字典树真正的存储形式，我们看下图：

这是一个包含三个单词‘sea’，‘she’，‘sells’的字典树完整形式。在这里插入图片描述【示例来自参考资料3】可以看到，Trie中一般含有大量的空链接。

C++实现 class Trie{ private: // 定义节点 bool flag = false; Trie* next[26] = {nullptr}; public： Trie(){} // 构造函数 void insert(string word){ // 插入 Trie* node = this; for(int i=0; i node->next[c-'a'] = new Trie(); } node = node->next[c-'a']; } node->flag = true; // 单词串的尾节点为true } bool search(string word){ // 查找单词是否存在Trie中 Trie* node = this; for(int i=0; i //查找前缀 Trie * node = this; for(int i=0; i

【本文地址】

Trie（字典树）详解与C++实现

Trie（字典树）详解与C++实现

今日新闻

推荐新闻