字典树

字典树按共享前缀存储字符串，每条边对应一个字符。它常用于自动补全与前缀路由。长度为 L 的插入、精确搜索、前缀搜索，平均时间为 O(L)。词尾标记区分完整单词与普通前缀。

car 和 cat 共用 c、a 两段路径，再从 r、t 分叉。走到一个节点证明前缀存在；节点上的词尾标记才证明完整单词存在。

每条边一个字符

根不保存字符。根的子映射按单词首字符索引，其余节点按下一个字符映射到子节点。节点表示从根走来的完整前缀，因此 c 下方的 a 表示 ca，不是整棵树中任意的 a。

insert(word) 从根逐字符读取。有对应子节点就复用，没有就创建；读完最后一个字符后，设置该节点的词尾标记。只插入 car 时，c -> a 路径存在，但 ca 不自动成为单词。

两种查询共用字符遍历。search(word) 要求路径完整且终点有词尾标记；startsWith(prefix) 只要求读完前缀，不检查词尾。所以 startsWith("ca") 到达节点即可，search("ca") 还需检查标记。

逐步演示

默认从空根开始，执行五项操作：

1. insert("car")：依次读取 c、a、r。三个子节点都不存在，逐个创建并进入，最后标记 r 为词尾。保存一个单词，单词字符总数为 3，字符节点数为 3。
2. insert("cat")：复用 c、a，只创建 t 并设词尾。两个单词共有六个字符，树只用四个字符节点；共享的 c、a 各存一次。
3. search("car")：走过 c、a、r，终点有词尾标记，返回 true。
4. startsWith("ca")：走过 c、a，路径存在，返回 true，不要求 a 是词尾。
5. search("ca")：到达同一个 a，但没有词尾标记，返回 false。同一条路径对应不同查询条件。

画布用琥珀色强调当前字符和边，已匹配前缀保留中等强调，无关分支淡出。勾选环表示完整单词，最后两项查询的区别就是是否要求该环。

时间与空间复杂度

L 为本次单词或前缀的字符数。

这里假设子映射的单次查询平均为 O(1)。字典树不逐个比较已存单词，而是读一次查询串，让每个字符选择一条边。一次选边为常数时间，不代表整次查询为 O(1)，因为最多仍要处理 L 个字符：查询在第一条缺失的边处提前停止，插入与成功的查询要读完 L 个。

Many words 场景保存八个词，再执行 search("cap")，仍只走 c、a、p 三条边。工作量取决于查询长度，而不是直接遍历八个词。

总存储为 O(P)，P 是所有词中不同非空前缀的数量。car、cat 的总字符数为 6，P 为 4。没有共享时，P 等于总字符数；No sharing 的 ant、boy、cup 共九个字符，需要九个字符节点。

只做精确成员查询时，哈希集合通常更简单，也可能更省内存。需要自动补全、前缀路由或列出 ca 下的键时，字典树的前缀路径才有价值。代价是每个节点的子映射和较差的内存局部性。

播放器最多显示 24 个字符节点，单词长度最多 6。这是标签可读性的限制；实际字典树按内存或应用规则增长。

边界情况

• 空树：对非空串进行两种查询，都在首字符因缺少子节点而失败。
• 单字符词：根直接指向该字符节点，词尾标记决定精确成员关系。
• 重复插入：复用全部节点，重复设置已有标记；节点数、词数、已存词的字符总数都不变。
• 词也是前缀：插入 car、care 后，r 既是词尾，也有子节点 e。
• 很少共享前缀：查询仍为 O(L)，但几乎每个字符都需独立节点，节省空间的效果消失。

常见错误

• 把可达路径都当作词。 插入 car 后，search("ca") 仍应为 false，必须检查词尾。
• 在 startsWith 中检查词尾。 前缀查询只要求路径，把词尾作为条件就变成了精确查询。
• 先进入不存在的子节点。 插入时先创建 children[ch]，再移动 node。
• 把根计为字符节点。 根只是入口，不存字符；比较共享效果时统计非根节点。
• 把整个操作算成 O(1)。 每次选子节点平均 O(1)，长度 L 的输入最多执行 L 次，因此为 O(L)。