二叉搜索树不成功搜索平均深度公式c(n)=2H(n−1)−2(n−1)/n推导求解

推导前提 #

我们讨论的是随机构建的二叉搜索树（BST）：即n个互不相同的键值按完全随机的顺序插入生成的BST，我们要推导的是该BST不成功搜索的平均深度，也就是孤立森林中定义的c(n)。 #

核心定义先明确 #

• 内部节点：BST中存储键值、执行分裂判断的节点，对应孤立树的分裂节点
• 外部节点（终端节点）：BST中没有子节点的空节点，是不成功搜索的终止位置，对应孤立树中存储单个样本的叶节点
• 节点深度：从根节点到该节点经过的边数，根节点深度为0

推导步骤 #

1. BST内外节点数量关系 #

对有k个内部节点的BST，外部节点的数量固定为k+1，可通过归纳法验证：

• 边界：k=0（空树）时，外部节点数为1，符合0+1=1
• 归纳：假设k=i时成立，新增1个内部节点时，会将1个外部节点替换为内部节点，同时新增2个外部节点，净增1个外部节点，因此k=i+1时外部节点数为(i+1)+1，成立

2. 成功/不成功搜索总路径长度关系 #

设：

• S：所有内部节点的深度之和，即成功搜索的总路径长度
• U：所有外部节点的深度之和，即不成功搜索的总路径长度
  可归纳证明两者满足固定关系：U = S + 2k，其中k为内部节点数量：
• 边界：k=1时，根节点深度为0，S=0；2个外部节点深度均为1，U=2，符合2=0+2*1
• 归纳：假设k=i时成立，新增1个深度为d的内部节点，会替换1个深度为d的外部节点，新增2个深度为d+1的外部节点，U的变化为-d + 2*(d+1) = d+2，S的变化为+d，因此U - S的增量为2，关系始终成立

3. 成功搜索平均深度递推求解 #

随机构建BST的成功搜索平均深度P(k) = S/k是经典结论：
第一个插入的键为根节点，其键值大小排名在1~k之间的概率均等，若排名为t，则左子树有t-1个内部节点，右子树有k-t个内部节点。所有子树节点的深度都比在子树内的深度多1，因此总路径长度递推式为：
S(k) = S(t-1) + S(k-t) + k-1
对所有可能的t取期望后，可解得递推式的闭式解：
P(k) = 2*(1+1/k)H_k - 4
其中H_k为第k个调和数，定义为H_k = 1 + 1/2 + 1/3 + ... + 1/k

4. 代入得到不成功搜索平均深度 #

不成功搜索的平均深度Q(k) = U/(k+1)，代入U = S + 2k可得：
Q(k) = (k*P(k) + 2k)/(k+1)
把P(k)的闭式解代入化简：

Q(k) = [k*(2*(1+1/k)H_k -4) + 2k]/(k+1)
     = [2(k+1)H_k -4k + 2k]/(k+1)
     = 2H_k - 2k/(k+1)

5. 对应孤立森林的c(n)定义 #

孤立森林中c(n)的参数n是终端节点（外部节点）的数量，也就是上式中的k+1 = n，因此k = n-1，将k替换为n-1代入Q(k)：
c(n) = Q(n-1) = 2H_{n-1} - 2(n-1)/n
和题目给出的公式完全一致。 #

调和数的近似说明 #

调和数的渐近展开为H_k ≈ ln(k) + γ，其中γ为欧拉常数，取值约为0.5772156649，因此H_{n-1} ≈ ln(n-1) + 0.5772156649，和题目描述的估算方法一致。 #

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