题干与适用场景
给定 /api、/api/users、/api/users/admin 等字符串键，实现一棵基数树。每条边保存一个非空字符串，每个节点可以保存一个值。支持 insert(key, value)、get(key)、longestPrefix(key) 和 delete(key)。除非题目另有说明，空键只允许作为根节点的值。面试官考察的是数据结构与推导，不是调用现成库。
面试官考察点
- 是否保持每条非根边非空、同一父节点下子边首字节不同的不变量。
- 能否在首次不匹配处拆分边，同时保留旧子树和值。
- 能否区分精确查找与最长前缀查找。
- 删除后是否只合并无值的单子节点，并给出按键长度计算的真实复杂度。
回答前需要澄清的问题
先问键按字节还是 Unicode 码点处理、是否区分大小写、重复插入是否替换值、是否需要并发，以及最长前缀返回匹配键、值还是两者。按字节实现最直接，复杂度按字节数计算；Unicode 规范化应由树外策略负责。若需要并发，应明确加锁或快照，不要暗示算法天然线程安全。
30 秒回答框架
每个节点保存边标签、可选值和按首字节索引的子节点。插入时比较剩余键和子边标签：完全匹配就下沉，部分匹配就在公共前缀处拆分成两个后缀。精确查找必须消耗完整键并落在有值节点。最长前缀查找沿路径记录遇到的最后一个有值节点。删除先清除值；若节点无值且只有一个子节点，就拼接标签并提升子节点。
分步骤深入解答
- 声明不变量。 根节点没有边标签，其他节点标签非空，同一父节点的子节点首字节不同。节点即使有子节点也可以有值，因此
/api与/api/users能共存。 - 按最长公共前缀插入。 设剩余键与子边标签的公共前缀为
p。若p为空，换一个子节点；若p等于整个子边，消耗它后递归；若p更短，创建标签为p的新父节点，把旧节点移到旧后缀下，再挂上新后缀，若新后缀为空则把值放在拆分节点。 - 查找。 精确查找逐边消耗，遇到不匹配或缺少子节点就失败。最长前缀查找先记录根值，再记录沿途每个有值节点，键消耗完时返回最后一次记录。
- 删除与压缩。 清除目标值。若节点无值且只有一个子节点，就拼接两个标签并提升子节点的子树；若仍有值或有多个子节点则保留节点，保证兄弟不变量。
- 复杂度。 子节点用哈希表时，每次操作最多比较输入键的字节数，因此时间为 O(k) 加哈希表开销，空间为所有键标签总字节数。路径压缩减少稀疏单链节点，但不会让长键变成常数时间。
- 测试对抗用例。 覆盖空键、单字符键、先插入长键再插入其前缀、反向插入、边中间拆分、重复替换、删除叶子、删除前缀值、删除唯一键，以及无匹配的最长前缀查询。
高质量示范回答
我会让每条边保存非空字节字符串，子节点按首字节存放。插入最关键：比较子边标签和剩余键，在第一次不匹配处拆分。拆分节点保存公共前缀，旧后缀继续携带原子树，新后缀挂上新值；如果新键正好结束，就把值放在拆分节点。查找逐边匹配，最长前缀查找记住最后一个有值节点。删除清值后，只合并无值且只有一个子节点的节点。
type node struct {
label string
value any
hasValue bool
child map[byte]*node
}
// common 短于 child.label 时：
parent := &node{label: common, child: map[byte]*node{}}
oldSuffix := child.label[len(common):]
child.label = oldSuffix
parent.child[oldSuffix[0]] = child
parent.child[newSuffix[0]] = &node{label: newSuffix, value: v, hasValue: true}实际代码要处理 newSuffix 为空，把值放在 parent；删除时只有 hasValue 为 false 且子节点恰好一个才合并。我会在每次变更后检查不变量，而不只验证几个示例查找。
常见错误
- 把基数树写成每字符一个节点 → 丢失路径压缩 → 使用非空边标签并比较整条标签。
- 拆边时丢弃旧值或子树 → 旧键消失 → 先把旧节点按后缀移入，再挂新后缀。
- 最长前缀一遇到值就返回 → 更具体路由丢失 → 在每个有值节点更新候选。
- 合并仍有值的节点 → 短键被误删 → 只合并无值的单子节点。
- 声称查找 O(1) → 仍需比较键 → 说明按键长 O(k)，并交代子节点索引成本。
追问及应对
如果键不区分大小写，怎么改？
在插入和查找前统一按一条明确规则规范化，例如 ASCII 转小写。不能只在查找时规范化，否则不同拼写会进入不一致路径。Unicode 折叠和规范化应作为独立策略说明。
如何支持通配路由段？
增加明确优先级，例如静态边优先于参数边，参数边优先于 catch-all。字面前缀仍可用基数树，但匹配会在不同边类型之间搜索，必须说明最大分支并测试歧义路由。
如何让树支持并发读写？
使用读写锁或写时复制快照。无锁方案还需要内存回收设计；只把根指针设为原子并不能让原地拆分和合并安全。把数据结构不变量与同步策略分开描述。