当前位置: 首页 > news >正文

数据结构 - 字典树 Trie

字典树(Trie)是一种树形数据结构,主要用于高效地存储和检索字符串集合。它通过利用字符串的公共前缀来节省存储空间,常用于词典查询、自动补全等场景。

1. 什么是字典树

字典树的每条边代表一个字符,从根节点到某一节点的路径表示一个字符串。如果某节点被标记为结束节点,则表示该路径对应的字符串存在于集合中。

2. 字典树的基本操作

字典树的核心操作包括插入和查找,时间复杂度通常为字符串长度的线性级别,比暴力搜索更高效。

2.1 树的构造

对于每个树的节点,应该包含以下字段:

  • 指向子节点的数组 children,数组长度为所有字符的数量;
  • 一个布尔变量 end,用于指定是否为字符串结尾。
2.2 插入节点
void insert(std::string word) {Trie *node = this;for (char c : word) {c -= 'a';if (node->children[c] == nullptr) {node->children[c] = new Trie();}node = node->children[c];}node->end = true;
}
2.3 查询
bool searchPrefix(std::string prefix) {Trie *node = this;for (char c : prefix) {c -= 'a';if (node->children[c] == nullptr) {return false;}node = node->children[c];}return node != nullptr && node->end;
}
2.4 代码模版
class Trie {
public:void insert(std::string word) {Trie *node = this;for (char c : word) {c -= 'a';if (node->children[c] == nullptr) {node->children[c] = new Trie();}node = node->children[c];}node->end = true;}bool searchPrefix(std::string prefix) {Trie *node = this;for (char c : prefix) {c -= 'a';if (node->children[c] == nullptr) {return false;}node = node->children[c];}return node != nullptr && node->end;}private:std::vector<Trie*> children;bool end;
};

3. 示例

208. 实现 Trie (前缀树)

http://www.hskmm.com/?act=detail&tid=24357

相关文章:

  • 激活函数实现
  • 漏洞赏金入门指南:从零开始的实战方法论
  • PMON failed to acquire latch 的报错及sqlplus / as sysdba 无法连接 - 详解
  • 2025CSP-S模拟赛58 比赛总结
  • 精读C++设计模式20 —— 结构型设计模式:桥接模式 - 详解
  • 用纯.NET开发并制作一个智能桌面机器人(六):使用.NET开发一个跨平台功能完善的小智AI客户端
  • 2025/10/4 总结
  • Qt处理Windows平板上摄像头
  • 你必须知道的TCP和UDP核心区别,快速搞懂这两大协议!
  • [swift 外部干涉法 extension]
  • 2025国庆Day3
  • 量子迁移计划启动:应对未来密码学挑战
  • HPE SPP 2025.09.00.00 - HPE 服务器固件、驱动程序和系统软件包
  • 详细介绍:Linux字符设备驱动开发全攻略
  • sql注入和xss漏洞
  • 数学 trick
  • 完整教程:精读C++20设计模式——行为型设计模式:解释器模式
  • js疑惑
  • 关于我
  • 20251004国庆模拟4
  • 珂朵莉树 ODT
  • 2025多校CSP模拟赛2
  • 详细介绍:深入了解linux网络—— 基于UDP实现翻译和聊天功能
  • Rewind: Codeforces Round 1055 (Div.1+Div.2)
  • 10.4模拟赛总结
  • 01.linux基础
  • 英语完形填空
  • 2025整体橱柜厂家TOP企业品牌推荐排行榜,云南昆明整体橱柜全瓷砖,开放式厨房,经济型,一站式无烟柴火灶,嵌入式,智能,多功能,全屋无烟柴火灶整体橱柜公司推荐
  • Centos7安装mysql8
  • vite-vue3脚手架(参考帝莎编程-后台管理系统开发)