Ternary tree（三叉树）搜索时间复杂度计算相关问题咨询

针对第一个疑问的结论 #

你的理解半对半错，需要补上明确的前提：

• 关于中间子节点遍历的描述完全正确：三叉搜索树的中间子节点对应「当前位置字符匹配成功，继续匹配下一位字符」的路径，只要待搜索字符串/前缀的长度为L，沿中间子节点向下遍历的次数就固定为L次，这部分开销和树中存储的字符串总数n没有直接关联。
• 关于左右子节点移动次数为log₃(n)的描述仅在平衡构造的三叉搜索树场景下成立：左右子节点的作用是在当前字符匹配层，查找和当前待匹配字符相等的节点，本质是这一层的三向搜索。平衡状态下，这部分查找的次数是对数级，但这里的对数底数是3，真数是当前字符位置上的不同字符总数，很多公开资料简化写为log₃(n)，是默认所有字符串长度接近、树结构完全平衡的理想假设。如果插入顺序导致树完全失衡（比如严格按字典序顺次插入所有字符串），最坏情况下左右移动的次数会退化为线性，达不到对数级别。

针对第二个疑问的结论 #

• 平衡三叉搜索树的搜索时间复杂度确实是O(L + log₃n)，你判断L是主导项的结论完全正确。
• 公开资料只提对数级复杂度，本质是两个常见的表述疏漏：
  • 部分资料把存储定长数据（比如整数）的平衡三叉树，和存储字符串的三叉搜索树搞混了：前者没有逐字符匹配的过程，复杂度就是纯对数级，直接套用到TST上属于概念错误。
  • 部分教材做复杂度分析时，默认待搜索的字符串是固定长度的短串（比如固定长度的状态编码、英文核心单词），此时L是常数，可以从复杂度表达式中省略，直接简化为O(log n)，但这个简化有严格的适用前提，不是通用结论。
• 实际场景下的复杂度权重很好判断：比如存储100万个字符串的平衡TST，log₃(1e6)的数值大概在12~13之间，如果待搜索的字符串长度是1000，这部分线性开销是对数项的近百倍，毫无疑问是复杂度的主导项。

课程作业作答提示：建议分场景写复杂度结论：无平衡优化的最坏场景下，TST搜索复杂度为O(L + n)；经过平衡优化的理想场景下，复杂度为O(L + log₃n)。工程实践中一般会通过随机插入、旋转平衡等方式避免树结构失衡，实际运行效率基本和待搜索串长度线性相关。

内容的提问来源于stack exchange，提问作者Jskoven