想请问 binary search tree 最好的情况下 height = log (n) , 但是 worst case = n
，n 是元素个数。那么要怎么证明 random 建立的 binary search tree height = log(n
) ??
实在是不太会这种要考虑到机率的情况，拜托大家解答了！谢谢！

CLRS没记错的话有，很长

你要先搞清楚你是要证明什么..是RBST的期望高度为O(lg n)还是RBST的高度为O(lg n) with high probability..第一种的性质比较弱 证明比较简单第二种就比较难一点 需要用到一些机率不等式..

请问F大,前者(期望高度)是指加入一个点的期望深度吗?

不是 你说的又稍微不一样了..

要证明的比较像是期望高度!