前缀树搜索与自动补全

功能说明

Trie 把单词逐字符存进嵌套字典，每个节点记录一个权重。insert 拒绝空串和负权重，重复插入会更新权重但不增加计数；complete 先走到前缀节点，再深度优先收集所有带权重的词，按权重降序、单词升序排序，最后截断到 limit 条。

关键代码

def walk(node: TrieNode, prefix: str, found: list[tuple[str, int]]) -> None:
    if node.weight > 0:
        found.append((prefix, node.weight))
    for char in sorted(node.children):
        walk(node.children[char], prefix + char, found)

遍历时对子节点排序，使收集顺序本身已是字典序；最终仍会按权重重新排序。

使用注意

• 权重为 0 表示“不是完整单词”，只作为中间节点存在，不会被补全结果返回。
• 递归深度等于最长单词长度，超长输入可能触发递归上限，必要时应改为显式栈。
• complete 会遍历整个前缀子树后再截断，前缀很短且树很大时开销明显。
• 插入是非线程安全的，多线程写入需要外部加锁。
• 字符串按 Python 字符切分，对大多数 Unicode 文本可用，但组合字符不会被归一化。

验证方式

示例应返回 [('rust', 10), ('runner', 7), ('runtime', 5)]，查询不存在的前缀返回空列表。可以插入同名词验证权重更新且 size 不变，再查询空前缀观察全部候选的排序。