如何证明随机插入构建的二叉树高概率高度为O(logn)

你不需要一开始硬啃Devroye 1986年的紧常数论文，证明*高概率树高为O(log n)*这个非紧结论有非常入门的推导路径，按以下顺序推进即可：

• 先补全必备的概率工具：你目前掌握的线性期望只能推出期望界，要证高概率界，先熟练掌握**切诺夫界（Chernoff Bound）**的简单形式，尤其是独立伯努利变量和的双侧尾概率上界，CLRS附录C和第5章末尾有完整的推导和基础习题，先做2-3道简单放缩题熟悉节奏，不需要提前学复杂的分支过程理论。
• 从非紧的简化证明入手，不要一开始追4.311的极限常数。O(log n)量级的高概率证明核心逻辑非常直白，全程不涉及超纲内容：

  论证框架：首先注意n个元素按随机顺序插入得到的BST，结构等价于随机排列对应的二分搜索树。对任意根到叶的路径，路径上每向下走一层，对应当前节点的键值把当前值域区间劈成左右两段，元素落在任意一段长度不小于原区间1/3的子区间的概率至少是2/3（这里常数可以随便取，不影响最终量级）。把单条路径长度超过c log n的事件用切诺夫界放缩，可将单条路径过长的概率压到n^{-2}量级，再用联合界对全部n个叶节点对应的路径取并，就能得到树高超过c log n的概率不超过1/n，即满足高概率要求。
  这个简化推导是绝大多数随机算法入门课程的标准讲义内容，不需要查学术论文，顺着“随机BST 高概率高度 Chernoff”的关键词找对应课程讲义即可，完整推导长度不超过2页。

• 摸透非紧界证明后再看Devroye的论文会顺畅很多：Devroye的工作本质上是把简化证明里“分裂概率取常数下界”的粗糙放缩，替换成了对分裂点分布的精确建模，结合分支过程的收敛性算出了极限常数4.311...，核心论证框架和简化证明是一致的，只是估计精度更高。
• 几个常见误区：
  • 习题只要求证明O(log n)的量级，不需要追求紧常数，常数c取10还是100都不影响结论的正确性
  • 不要混淆随机BST和均匀随机二叉树的分布，二者结构概率不同，不要套错分析模型
  • 不要跳过联合界的步骤，单条路径的尾界不能直接推出全局树高的界，必须对所有可能路径取并放缩

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