向AVL树插入递减序列时平衡操作数的归纳法证明

定义与基础观察 #

先明确两个核心定义：

• T(n)：向空AVL树插入n, n-1, ..., 1这n个递减数字时，累计的平衡旋转次数。
• h(n)：插入完成后AVL树的高度（定义：根节点到叶子节点的最长路径包含的节点数，单节点树高度为1）。

从示例可验证基础关系：

• n=1：仅插入1，无旋转，T(1)=0，h(1)=1，满足T(1)=1 - h(1)。
• n=2：插入8、7，树为左斜链，无旋转，T(2)=0，h(2)=2，满足T(2)=2 - h(2)。
• n=3：插入8、7、6后触发1次旋转，T(3)=1，旋转后树高度为2，满足T(3)=3 - h(3)。

我们先证明精确结论T(n) = n - h(n)，再推导近似结论。

归纳法证明 #

基础情况 #

对于n=1、2、3，上述观察已验证T(n) = n - h(n)成立。

归纳假设 #

假设对于所有k < n，T(k) = k - h(k)成立，且插入k到1后的树是高度为h(k)的合法AVL树。

归纳步骤 #

插入第n个数字（即1）时，新节点会被添加到当前树的最左叶子位置，此时分两种情况：

1. 无需旋转：插入后，树的所有节点左右子树高度差仍≤1。此时树的高度h(n) = h(n-1)+1，旋转次数T(n)=T(n-1)。
   根据归纳假设：
   T(n) = T(n-1) = (n-1) - h(n-1) = n - (h(n-1)+1) = n - h(n)，等式成立。

2. 需要旋转：插入后，某节点出现左左型不平衡（左子树高度比右子树高2），需执行1次右旋调整。旋转后树的高度h(n) = h(n-1)（旋转不改变整棵树的高度），旋转次数T(n)=T(n-1)+1。
   根据归纳假设：
   T(n) = T(n-1)+1 = (n-1 - h(n-1)) + 1 = n - h(n-1) = n - h(n)，等式成立。

两种情况均满足T(n)=n - h(n)，因此归纳结论成立。

近似结论推导 #

AVL树的高度h(n)是对数级别的：对于任意n，h(n) ≤ log_φ(2n+1)（其中φ≈1.618为黄金分割比），当n足够大时，h(n) ≈ log₂n（不同底数的对数仅差常数因子，近似时可忽略）。

代入精确结论可得：
T(n) = n - h(n) ≈ n - logn

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