---
title: "trie树"
created: 2025-11-28
tags:
  - 算法
---

# trie树

用二维数组模拟树 第一维放“结点” 第二维放该节点的孩子下标

trie是快速存储**字符串集合**的数据结构

如 abc ace bdf bd

从根结点出发 不断对孩子进行选择 选择从哪边往下走

插入是没有就建 查询是没有就失败

和哈夫曼编码很像

使用多叉链表很容易实现

不过 这里还是使用数组去模拟实现

不外乎就是存储根节点和子节点

子节点实际上又是一个根节点

两个根节点之间是通过子节点（关系）联系起来的

所以可以把子孩子存储为一个索引

（类似于e数组的东西 存根节点信息 类似于ne数组的东西 存子节点 表示某个根结点下面有哪些子结点）

但这两者间不仅仅只是下标对应的关系

还存在着一种父子间的关系

发现其实可以用二维去模拟

第一维存各个结点的信息

第二维则是对于单个结点来说 有哪些结点与它有关系

这个二维放的应该就是1维中的下标

跟之前一样 还是物理位置顺序 idx表示当前可用位置

head表示整棵树的根结点 指向0号位置吧

第一维没什么问题 就是有多少个结点就定义多大

第二维有一个注意点就是

字母一共就26个 对于每个结点来说 它至多有26个孩子

所以可以开辟第二维大小为27（0~26 留一个\0）

它里面存放的是跟它有关系的结点 在一维的下标

但是这个二维的下标还没被用到实处

其实可以直接对应为26个字母

用字符减去’a’ 得到abc……对应的下标为012……

一个位置就表示一个字母

要校检某结点是否存在字母a 只需要在a-’a’也就是该维的第二维的0处看是否有内容

如果有 就跳到它记录的那个下标那一维去 如果没有就说明不存在 至于如何操作看是在进行查询还是插入 查询的话直接说失败 插入的话 就在第一维的idx处插入这个新结点
并且在这个地方记录那个新结点的下标

- [[2-Learning/02-算法/03-刷题理模型/串相关模型/字典树/trie树/trie树|trie树]]

- [[2-Learning/02-算法/03-刷题理模型/串相关模型/字典树/trie树/trie变形 存二进制位|trie变形 存二进制位]]

---
⬅️ [[解码|解码]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/串相关模型/字典树/trie树/trie变形 存二进制位|trie变形 存二进制位]]