相同前缀共用路径
在普通字典树中,一层处理键的下一个字符或选定单位。具有相同开头的键沿同一段路径前进,直到不同的位置才分支。节点上的结束标记或关联值,区分“某个键恰好到这里结束”与“这里只是其他长键的前缀”。
这一区分很重要:若已经存放某个长词,不能因为走到其中一半,就把尚未单独加入的短词也当成已存在的键。查找需要同时核对路径是否存在,以及对应结束位置是否承载有效条目。
精确命中与前缀查询分开
前缀枚举先走到给定前缀的位置,再收集它下面的有效键;最长前缀查询则沿输入继续前进,保留最近一次遇到的有效结束位置。二者回答的问题不同,也都不同于“输入是否就是一个完整已存键”。
例如路由前缀或自动补全可以利用这些关系,但最终含义仍由应用规定。字典树按输入单位匹配,不会自动判断两个名字是否指同一对象,也不会凭相似开头为不同词语补出语义关系。
字符范围与分支存储影响成本
用每个字符一个分支的直接表示,查找工作通常与键长有关;Princeton的256路示例便为核心操作给出与键长度成比例的界。若要枚举大量结果,还必须计算输出本身的数量与长度,不能只看走到前缀位置花了多少步。
每个节点分配整个字符表的子链接数组,可能给稀疏分支带来空间开销。三向搜索字典树等表示选择不同的分支结构。实现还须先明确键按字节、字符或其他单位处理,以及大小写、规范化与字符范围的接口规则。