想請問 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大,前者(期望高度)是指加入一個點的期望深度嗎?

不是 你說的又稍微不一樣了..

要證明的比較像是期望高度!