Randomized Binary Search Tree 平均深度證明

一棵Randomized Binary Search Tree ，平均深度為2logn
其每個節點成為該顆子樹的根的機率有1/(該顆子樹的大小+1)
對於[分裂/合併式][Split / Merge] Randomized Binary Search Tree 亦同
而其等價於在BST中進行隨機插入
這裡提供嚴謹的證明 連結
以下簡略的證明原自於陳柏叡大大(數奧國手)親筆所寫:

現在總共有n個數，要證說對他隨機排序之後一個一個插入BST得到的平均最大深度=2logn。
那看任意一個數x，他的祖先個數就是它的深度，所以只要算x的祖先個數的期望直。
這只要算，對x以外的每個數y，y當x的祖先的機率是多少，再把他們加起來即可。

但注意到，假設在這n個數(由小到大)排序好的序列裡面，x 排在第 i 個， y 排在第 j 個(  y 可以 <x，所以 j 可以 < i  )，那麼落在 [ i , j ] ( 或 [ j , i ] )這個區間裡的所有數， y 是第一個被插入BST的(否則會和 y 是 x 的祖先矛盾)，而這件事情發生的機率為 1/(  | i - j | +1 ) 。
也就是，如果一個數 y 和 x 在排序好的序列裡面的坐標差 = d 的話，那麼 y 當 x 的祖先的機率就是 1/(d+1)。

所以如果 x 是排序好的序列裡的第 i 個，那所求是
1 / i + 1 / ( i - 1 ) + ... + 1/2 + 1/2 + 1/3 + ... + 1/( n - i + 1 )
<= 2 ( 1/2 + 1/3 + ... + 1/n )
約 = 2logn