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

【恋上数据结构】前缀树 Tire 学习笔记

news 2025/7/22 13:08:38

Tire

需求分析

如何判断一堆不重复的字符串是否以某个前缀开头？

  • 用 Set\Map 存储字符串（不重复）
  • 遍历所有字符串进行判断
  • 缺点：时间复杂度 O(n)

有没有更优的数据结构实现前缀搜索？

Tire（和 Tree 同音）

简介

  • Trie 也叫做字典树、前缀树 (Prefix Tree)、单词查找树。
  • Trie 搜索字符串的效率主要跟字符串的长度有关。

假设使用 Trie 存储 cat、dog、doggy、does、cast、add 六个单词，结果如下所示

在这里插入图片描述

接口设计

有两种设计方案：

  1. 第一种仅仅是存储字符串。（像 set 集合）
  2. 第二种是存储字符串的同时可以再存储一个 value（像 map 接口）

分析：

第二种设计方案更为通用，比如说我们要做一个通讯录，以某个人的姓名作为 key，然后以他的详细信息作为 value（其他电话号码、邮箱、生日等各种详细信息）

public interface Trie <V> {int size(); boolean isEmpty(); void clear(); boolean contains(String str); V add(String str, V value); V remove(String str); boolean starswith(String prefix);
}

在这里插入图片描述

Node 设计

孩子节点集合解析（HashMap<Character, Node<V>> children;）：

  • key 相当于代表的是路径值，Character 字符类型可以是英文也可以是中文
  • value 是嵌套了当前节点下的所有子节点，方便后面节点值寻找
  • word：true 为已存储单词（红色），false 为非单词（蓝色）
    /*** Trie 中的节点类，包含父节点、孩子节点集合、字符、值以及表示是否为一个完整单词的标志。** @param <V> 值的类型*/private static class Node<V> {Node<V> parent; // 父节点HashMap<Character, Node<V>> children; // 孩子节点集合Character character; // 字符，为删除做准备V value; // 节点对应的值，也就是整个单词boolean word; // 是否为单词的结尾（是否为一个完整的单词）/*** 构造函数，初始化节点时需要指定父节点。(在添加节点时用到）** @param parent 父节点*/public Node(Node<V> parent) {this.parent = parent;}}

完整代码实现附注释

/*** Trie（字典树）数据结构，用于存储字符串集合，支持添加、查询、删除等操作。** @param <V> 值的类型*/
public class Trie<V> {/** Trie 中存储的单词数量 */private int size;/** 根节点 */private Node<V> root;/*** Trie 中的节点类，包含父节点、孩子节点集合、字符、值以及表示是否为一个完整单词的标志。** @param <V> 值的类型*/private static class Node<V> {Node<V> parent; // 父节点HashMap<Character, Node<V>> children; // 孩子节点集合Character character; // 字符，为删除做准备V value; // 节点对应的值，也就是整个单词boolean word; // 是否为单词的结尾（是否为一个完整的单词）/*** 构造函数，初始化节点时需要指定父节点。(在添加节点时用到）** @param parent 父节点*/public Node(Node<V> parent) {this.parent = parent;}}/*** 获取 Trie 中存储的单词数量。** @return Trie 中存储的单词数量*/public int size() {return size;}/*** 判断 Trie 是否为空。** @return 如果 Trie 为空，则返回 true；否则返回 false*/public boolean isEmpty() {return size == 0;}/*** 清空 Trie，将单词数量重置为 0。*/public void clear() {size = 0;root = null;}/*** 根据指定的键获取对应的值。** @param key 键* @return 如果键存在且是一个完整的单词，则返回对应的值；否则返回 null*/public V get(String key) {Node<V> node = node(key);return (node != null && node.word) ? node.value : null;}/*** 判断 Trie 是否包含指定的键。** @param key 键* @return 如果 Trie 包含指定的键且是一个完整的单词，则返回 true；否则返回 false*/public boolean contains(String key) {Node<V> node = node(key);return node != null && node.word;}/*** 添加键值对到 Trie 中。如果键已经存在，则更新对应的值；否则新增一个单词。** @param key   键* @param value 值* @return 如果添加的键已经存在，则返回对应的旧值；否则返回 null*/public V add(String key, V value) {keyCheck(key);// 创建根节点if (root == null) {root = new Node<>(null);}// 获取 Trie 根节点Node<V> node = root;// 获取键的长度int len = key.length();// 遍历键的每个字符for (int i = 0; i < len; i++) {// 获取当前字符char c = key.charAt(i);// 判断当前节点的孩子节点集合是否为空boolean emptyChildren = (node.children == null);// 获取当前字符对应的孩子节点Node<V> childNode = emptyChildren ? null : node.children.get(c);// 如果当前字符对应的孩子节点为空，说明该字符在当前节点的孩子节点集合中不存在if (childNode == null) {// 创建新的孩子节点，并将其加入到当前节点的孩子节点集合中childNode = new Node<>(node);childNode.character = c;// 判断孩子节点集合是否为空的同时，避免了每次都要创建新的 HashMap 对象，提高了效率node.children = emptyChildren ? new HashMap<>(16) : node.children;node.children.put(c, childNode);}// 将当前节点移动到其对应的孩子节点上，继续下一层的遍历node = childNode;}// 1 - 已经存在这个单词, 覆盖, 返回旧值if (node.word) {V oldValue = node.value;node.value = value;return oldValue;}// 2 - 不存在这个单词, 新增这个单词node.word = true;node.value = value;size++;return null;}/*** 移除 Trie 中的指定键。如果键存在且是一个完整的单词，将其从 Trie 中移除。** @param key 键* @return 如果键存在且是一个完整的单词，则返回对应的值；否则返回 null*/public V remove(String key) {Node<V> node = node(key);// 如果不是单词结尾，不用作任何处理if (node == null || !node.word) {return null;}size--;V oldValue = node.value;// 如果还有子节点if (node.children != null && !node.children.isEmpty()) {node.word = false;node.value = null;return oldValue;}// 没有子节点Node<V> parent = null;while ((parent = node.parent) != null) {parent.children.remove(node.character);if (parent.word || !parent.children.isEmpty()) {break;}node = parent;}return oldValue;}/*** 判断 Trie 是否包含指定前缀。** @param prefix 前缀* @return 如果 Trie 包含指定前缀，则返回 true；否则返回 false*/public boolean startsWith(String prefix) {return node(prefix) != null;}/*** 根据传入字符串，找到最后一个节点。* 例如输入 dog* 找到 g** @param key 键* @return 如果键存在，则返回对应的节点；否则返回 null*/private Node<V> node(String key) {keyCheck(key);Node<V> node = root;int len = key.length();for (int i = 0; i < len; i++) {if (node == null || node.children == null || node.children.isEmpty()) {return null;}char c = key.charAt(i);node = node.children.get(c);}return node;}/*** 检查键是否合法，不允许为空。** @param key 键*/private void keyCheck(String key) {if (key == null || key.length() == 0) {throw new IllegalArgumentException("key must not be empty");}}
}

总结

  1. Trie 的优点：搜索前缀的效率主要跟前缀的长度有关

  2. Trie 的缺点：需要耗费大量的内存（一个字符一个节点），因此还有待改进

  3. 更多 Trie 相关的数据结构和算法

    • Double-array Trie、Suffix Tree（后缀树）、Patricia Tree、Crit-bit Tree、AC 自动机
http://www.lryc.cn/news/256480.html

相关文章：

  • 2023五岳杯量子计算挑战赛数学建模思路+模型+代码+论文
  • Angular中的单向和双向数据绑定
  • 【Vue】vue整合element
  • HarmonyOS应用开发者高级认证考试答案
  • 6、Broker消息处理流程（六）
  • Clean 架构下的现代 Android 架构指南
  • 代码随想录算法训练营第四十六天| 139 单词拆分
  • IEEE期刊论文模板
  • 上位机与PLC：ModbusTCP通讯之数据类型转换
  • 界面控件DevExpress WPF导航组件，助力升级应用程序用户体验！（上）
  • 联合基于信息论的安全和隐蔽通信的框架
  • 行业地位失守，业绩持续失速，科沃斯的故事不好讲
  • 蓝桥杯：货物摆放--因数存到数组里的技巧--减少运算量的方法
  • 我的创作纪念日——一年
  • Windows server 部署iSCSI共享磁盘搭建故障转移群集
  • 2023年山东省职业院校技能大赛信息安全管理与评估二三阶段样题
  • 数据结构——栈与栈排序
  • Java Web应用小案例 - 实现用户登录功能
  • Excel——多列合并成一列的4种方法
  • Vue笔记（四）路由
  • Redis部署-哨兵模式
  • 滑动窗口练习（三）— 加油站问题
  • udemy angular decoration 自存
  • msvcr90.dll丢失的解决方法分享，5个快速修复dll文件丢失教程
  • 海外媒体发稿：软文发稿推广技巧解析超级实用-华媒舍
  • vm net 方式 静态ip配置访问主机IP和外网
  • Vue笔记（二）基本语法
  • 前端面试提问（4）
  • 基于BEV+Transformer的地面要素感知+建模技术在高德的应用
  • 了解c++11中的新增