企业官网建设流程全解析

仙游哪里可以做网站的,浙江台州网络设计网站,如何制作自己的二维码,哈尔滨网站建设丿薇1.什么是Trie树Trie树#xff0c;又叫字典树、前缀树#xff08;Prefix Tree#xff09;、单词查找树 或 键树#xff0c;是一种多叉树结构。如下图#xff1a;上图是一棵Trie树#xff0c;表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “…1.什么是Trie树Trie树又叫字典树、前缀树Prefix Tree、单词查找树 或 键树是一种多叉树结构。如下图上图是一棵Trie树表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质根节点不包含字符除根节点外的每一个子节点都包含一个字符。从根节点到某一个节点路径上经过的字符连接起来为该节点对应的字符串。每个节点的所有子节点包含的字符互不相同。通常在实现的时候会在节点结构中设置一个标志用来标记该结点处是否构成一个单词关键字。可以看出Trie树的关键字一般都是字符串而且Trie树把每个关键字保存在一条路径上而不是一个结点中。另外两个有公共前缀的关键字在Trie树中前缀部分的路径相同所以Trie树又叫做前缀树Prefix Tree。我们可以举个例子原字符串集合{ abcde 、aced 、bcdf 、bcff }插入字符串aced 、cdaa新字符串集合{ abcde 、abde、aced 、bcdf 、bcff 、cdaa }说明图中 ※ 为 字符串结束的标记 。若某结点上有标记 ※则说明 从根结点 到该结点为止每个结点表示的字符 相连 组成的字符串存在于集合中。相应的对于 没有标记 的结点串联成的字符串只是原有字符串的 一部分 不属于 字符串集合。2.字典树的应用场景当我们在字典树的每⼀个结点位置额外维护⼀些信息时就可以做到很多事情查询某个单词是否出现过并且出现⼏次查询有多少个单词是以某个字符串为前缀查询所有以某个前缀开头的单词这个作⽤可以⽤到输⼊法中输⼊拼⾳的时候可以提⽰可能 的单词当然除了上述作⽤以外字典树还可以解决别的问题后续可以在做题中体会。3.字典树的实现基本结构字典树的每个节点包含子节点指针通常是一个数组或映射一个标志位表示从根节点到该节点的路径是否构成一个完整的单词可能包含其他辅助信息如词频这里需要理解一个非常重要的问题怎么理解idx3.1. 插入 ( insert ) 操作将字符串 逐个拆分 成 单个字符从第一个字符开始与 Trie 树的 根结点开始 的 子结点 比对若有结点具有 相同 的字符则以同样的方式对比 下一个字符 与该结点的 子结点 。举例在 图 1 中插入字符串 abde ( 拆分a/b/d/e)对于字符 a 根结点 的 子结点 中有 a 向后判断 下一个字符 b 与 结点 a 的 子结点对于字符 b a 结点的 子结点 中有 b 向后判断下一个字符 d 与 结点 b 的子结点对于字符 d b 结点的子结点中 没有 d 因此要创建新结点 d向后 判断下一个字符 e 与 结点 d 的 子结点对于字符 e d 结点的子结点中没有 e 因此要创建新结点 e( 从创建了一个新结点起后面剩下的字符显然都要创建新的结点但其 操作和之前的判断相同 )举例在 图 2 中插入字符串 cdaa ( 拆分c/d/a/a)对于字符 c 根结点的子结点中没有 c 因此要创建新结点 c剩下的字符 daa 以相同的操作逐个创建以存储字符串。注意在插入完字符串之后要给末尾的结点加上 结束标记。现在我们就能写出代码了首先我们先定义好我们需要的一些数据结构。#include iostream using namespace std; const int N 100010; int son[N][26]; // 存储每个结点的所有儿子结点 // 在题目中字符串只包含 26 个小写字母 // 因此每个结点最多只会向外连 26 条边 ( 最多只有 26 个儿子结点 ) int e[N]; // count记录以这个结点结尾的单词有多少个 // 它在本模板中作为 字符串结束标记 int idx; // 存储当前已经使用到的结点的下标 // 下标是 0 的结点既是根节点又是空结点 int p[N]; //记录每个节点被经过的次数, //p[i] 表示有多少个单词的前缀经过节点 i。例如根节点的 p[0] 等于插入的单词总数因为所有单词都从根节点开始。这里先回答一个问题如何理解idx?idx 是字典树中节点的动态分配标识符用于唯一标记每一个新创建的节点。它的核心作用是唯一性确保每个新节点有唯一的索引避免路径冲突。动态扩展按需分配节点无需预先固定树的结构。为什么需要 idx字典树的本质是用节点路径表示字符串例如字符串 apple 的路径是根节点 → a → p → p → l → e根节点的索引固定为 0。其他节点需要动态创建例如根节点的子节点 a 可能对应索引 1。a 的子节点 p 可能对应索引 2依此类推。idx 的作用就是为这些新创建的节点分配一个全局唯一的索引确保路径的唯一性。idx 的工作流程初始化程序开始时idx 0根节点已存在无需分配。插入字符串当需要创建新节点时执行 son[cur][path] idx。idx 会先递增 idx再将新值赋给节点。例如第一个新节点的索引是 1第二个是 2依此类推。具体示例假设插入字符串 abc根节点 0p[0]根节点被经过次数1。字符 a 对应路径 0path a-a 0。检查 tree[0][0]若未创建初始为0则分配新节点 tree[0][0] idx 1。节点 1p[1]经过次数1。字符 b 对应路径 1。检查 tree[1][1]若未创建分配 tree[1][1] idx 2。节点 2p[2]。字符 c 对应路径 2。检查 tree[2][2]若未创建分配 tree[2][2] idx 3。结束1. e[3]标记字符串结尾。最终树的结构为根节点 (0) → a (1) → b (2) → c (3)关键问题解答为什么不用固定索引字符串的组合是无限的无法预先确定需要多少节点。idx 按需分配节省内存。idx 会重复吗不会。idx 严格递增每个新节点分配的索引唯一。idx 和数组大小 N 的关系N 需足够大如 1e6否则 idx 超过 N 会导致数组越界。接下来我们就能写出这个代码// 插入字符串到字典树 void insert(string s) { int cur 0; // 从根节点索引0开始遍历 p[cur]; // 根节点被经过次数1总单词数统计 for (auto ch : s) // 遍历字符串的每个字符 { int path ch - a; // 将字符转换为路径编号a0, b1...z25 // 如果当前路径不存在则创建新节点 if (son[cur][path] 0) { son[cur][path] idx; // 分配新节点idx递增 } cur son[cur][path]; // 移动到子节点 p[cur]; // 当前节点经过次数1 } e[cur]; // 循环结束时cur位于字符串末尾节点标记单词结尾次数1 }3.2. 查询 ( query ) 操作与插入操作的原理基本相同将需要查询的字符串 逐个拆分 成单个字符逐个与 Trie 树中的结点比较直至发现 Trie 树中 不存在 的字符或要查询的字符串的各个字符都 比较完成 。对于发现 Trie 树中不存在的字符一旦发现就能确定要查询的字符串不属于原集合。举例在图 3 中查询 acwing 能找到 a → c 但 c 的子结点中没有 w 则确定集合中不存在该字符串对于要查询的字符串的各个字符都比较完成则存在两种情况① 要查询的字符的确属于集合② 要查询的字符是集合中某个字符串的前缀。举例在图 3 中查询 ac 能找到 a → c 字符串比较完成。因为 ac 是原有字符串 aced 的一部分 ( 前缀 )。此时就需要用到结点上的 字符串结束标记 了。在 ac 的查询过程中最后判断的结点落在了结点 c 上但该结点没有 字符串结束标记 因此可以判断 ac 不属于原集合。举例在图 3 中查询 aced 最后判断的结点落在了结点 d 上该结点具有 字符串结束标记 因此可以判断 aced 属于原集合。查询完整字符串出现的次数// 查询完整字符串出现次数 int find(string s) { int cur 0; // 从根节点开始查找 for (auto ch : s) { int path ch - a; if (son[cur][path] 0) { return 0; // 路径不存在说明单词不存在 } cur son[cur][path]; // 沿路径向下移动 } return e[cur]; // 返回结尾节点的单词计数 }查询有多少个单词以字符串s为前缀// 查询以s为前缀的单词数量 int find_pre(string s) { int cur 0; for (auto ch : s) { int path ch - a; // 原代码中的get_num(ch)应为ch-a否则无法编译 if (son[cur][path] 0) { return 0; // 前缀路径不存在 } cur son[cur][path]; } return p[cur]; // 返回该前缀最后一个节点的经过次数 }复杂度分析操作时间复杂度空间复杂度插入O(L)O(L)查找O(L)O(1)前缀搜索O(P)O(1)L: 单词长度P: 前缀长度变体与优化1. 压缩字典树Radix Tree合并只有一个子节点的路径进一步节省空间2. 双数组字典树用两个数组代替指针内存更紧凑访问更快3. 后缀树存储字符串的所有后缀用于字符串匹配、查找最长重复子串总结字典树是处理字符串相关问题的强大工具特别适合前缀匹配、自动补全和字典查找场景。虽然在某些情况下内存开销较大但其O(L)的查询时间复杂度和优雅的前缀处理能力使其在许多实际应用中不可或缺。选择使用字典树时需要根据具体需求考虑字符集大小、内存限制和查询模式必要时可以采用压缩优化或混合数据结构来平衡性能与资源消耗。