扩展平衡因子范围的高度平衡BST搜索时间复杂度解析（面试问题答疑）

面试问题回顾：给定一棵高度平衡BST，其平衡因子定义为「左子树高度 - 右子树高度」，允许的平衡因子取值为0、1、-1、2、-2。请问在这类高度平衡BST中搜索一个元素的时间复杂度是多少？我当时的回答是：相较于标准平衡BST仅允许平衡因子为0、1、-1的定义，即便该BST允许平衡因子为2或-2，其搜索操作的时间复杂度仍应为O(logN)（其中N为树中元素的数量），因为当N足够大时，平衡因子取值为1还是2不会产生显著影响。想确认这个结论是否正确，并得到严谨的解释。

你的结论是完全正确的，不过可以用更严谨的推导来支撑这个结论——核心在于这类BST的高度依然是对数级的，而BST的搜索时间复杂度直接由树的高度决定。

关键推导：树的高度是O(logN) #

BST的搜索操作是沿着从根到目标节点的路径遍历，路径长度等于树的高度，所以我们只需要证明：允许平衡因子±2的BST，其高度h(N)与节点数N的关系是h(N) = O(logN)。

我们可以通过最小节点数递推来证明：
设m(h)为高度为h的这类BST所需的最少节点数。为了让高度最大化（即相同节点数下树最高），我们会构造一棵“最不平衡”的合法树：根节点的一棵子树高度为h-1，另一棵子树高度为h-3（因为平衡因子最大为±2，所以两棵子树的高度差最多是2）。

由此得到递推公式：

m(h) = m(h-1) + m(h-3) + 1

初始条件：

• m(0) = 0（空树）
• m(1) = 1（仅根节点）
• m(2) = 2（根+一个子节点）

计算前几项可以看到：
m(3)=3, m(4)=5, m(5)=8, m(6)=12, m(7)=18...

这个递推式的增长速度是指数级的（类似斐波那契数列，只是递推步长为3），也就是说m(h)与某个大于1的常数的h次方成正比（比如解特征方程x³ = x² + 1，得到的主根约为1.465）。反过来推导，当节点数为N时，树的高度h(N)必然是log(N)的量级——因为N ≥ m(h)，所以h ≤ log_φ N（φ是上述指数增长的底数），即h(N) = O(logN)。

结论 #

既然树的高度是O(logN)，那么搜索操作的时间复杂度自然也是O(logN)。你当时的结论没问题，只是解释可以更精准：不是“平衡因子1或2没显著影响”，而是只要树的高度被限制在对数级，不管平衡因子的上限是1还是2（甚至更大的常数），搜索的时间复杂度都保持对数级——因为指数增长的节点数对应对数级的高度，这才是核心逻辑。

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