※ 引述《winnie48 (winnie)》之铭言：
: 想请问 binary search tree 最好的情况下 height = log (n) , 但是 worst case = n
: ，n 是元素个数。那么要怎么证明 random 建立的 binary search tree height = log(n
: ) ??
: 实在是不太会这种要考虑到机率的情况，拜托大家解答了！谢谢！
给定 n 个元素为插入 BST 的元素集合。
假设插入BST的顺序是均匀随机分布。
此时建出来的树 T 本身就是一个随机物件。
那T的高度 Height(T) 也是一个随机变量
所以 Height(T) 的期望值就是期望高度 = E[Height(T)]
可以证明为O(lg n)。
但是这性质很弱，因为他只证明期望值，没有提供concentration。
所以需要一个比较强的性质，像是
Pr(Height(T) > c * lg n) = o(1)
也就是，T的高度大于 c * lg n的机率很小。
不过这证明起来比较麻烦。
插入的期望深度又稍微不一样，要看你怎么定义插入的东西。
令D(x, T)表示把 x 插入到 T 的深度。
如果插入的元素是任意的，讨论worst case。
你是在找 Max_x E[D(x, T)]，注意这时候T是随机变量。
Max_x E[D(x, T)]应该顶多比 E[Height(T)] 多一而已。
如果插入的元素是随机的（你要先定义好随机的意义是什么）
你是在找 Avg_x E[D(x, T)]，不过这数值不可能大于Max_x E[D(x, T)]
举例来说，令 T 中的元素是 a1, ..., an, 且ai <ai+1，
假设随机的意义是 x 在 ai和ai+1中间的机率是均等的 for all i。
此时Avg_x E[D(x, T)] 必定会小于 Max_x E[D(x, T)]。