\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年1月17日 星期六

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

沒有留言:

張貼留言