\( \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月15日 星期四

[分裂/合併式] 隨機二分查找樹 [Split / Merge] Randomized Binary Search Tree

今天來講解可以做區間處理的Randomized Binary Search Tree
好比treap,可以利用拆分跟合併的方式來做區間處理
感謝伯恩大神的指導,請參考其網站

寫起來並不會比需要旋轉的難
先定義他的節點:
可以在裡面增加一些懶惰標記的更新(min,max,rev...等等)

計算節點大小

主要利用[分裂/合併]來進行區間處理
接下來講解分裂(參見 treap分裂):
這是將o按中序將前k個節點分到a,剩下的分到b

合併(參見 treap合併):
這就是隨機的精華所在
每次merge時,a有size(a)/(size(a)+size(b))的機率將a作為root
b反之亦然
而本來random是這樣寫的:
但是看了丁安立魔法師的blog,發現只要x++就好了,也不知道為甚麼

如果只是要做普通的二分搜尋樹,可以利用排名來求出其在整顆樹中的名次,然後再相對應處做插入
插入data可以寫成:
bst.insert(data,bst.rank(data));
刪除也可以用類似的方法處理

旋轉式的randomize bst就可以做這些處理了(其實分裂合併式bst速度有點慢),那為何還需要 分裂/合併 呢?
我們可以把整顆樹的中序走訪看成是一條陣列
-->因此可以利用它來作區間的維護

像是區間的最大最小值,區間反轉啦,區間移動、刪除等等都可以利用它在logn的時間完成
只須修改其up跟down函數就可以達成目的
凡是線段樹能做到的事情,他都能做到,可以用它來解決很複雜的區間處理問題

注意的是,在有懶惰標記的情況下,如果要詢問一個區間必須在切出那塊區間後先進行down的操作再進行詢問,否則懶惰標記可能沒有被推下去,範例如下:

這個範例up()跟down()也要重寫:

因為應用時分靈活,故不提供樣板,只做介紹

沒有留言:

張貼留言