\( \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年2月19日 星期四

[ scapegoat tree ] 替罪羊樹

替罪羊樹論文其中一個作者,Ronald Linn Rivest,同時也是RSA加密算法的R
替罪羊樹是一種不需要旋轉的平衡樹,它會要求使用者給定一個\(\alpha\)值,其值介於0.5到1之間,\(\alpha\)越大,插入就越快,查詢就越慢,實驗發現\(\alpha\)介於0.55~0.75是最佳的,但是具體的值要看使用者的要求
其平衡滿足:
1.
    \(\alpha*size(o) \le size(o \to left)\)
    \(\alpha*size(o) \le size(o \to right)\)
2.
    \(deep(o) \le log_{1/\alpha} (size(tree))\)
當插入節點導致條件2.不滿足時,會往上回溯到第一個不滿足的節點,然後重建這顆節點的子樹成為完美平衡的二元樹
刪除可以用一般的BST刪除法,當不滿足條件時往上回溯到最先不滿足的節點,重建子樹,也可以懶惰刪除,先設立一個標記, 要刪除這個節點就把它做記號,當\(\alpha\)*全部的節點數量>實際上存在的節點數量,就重建這顆子樹
本文提供一般刪除的方法

其實替罪羊樹的節點是不需要記錄其size的,因為若需要重建,求得size的時間複雜度與重建的時間複雜度相等,這裡為了支援其它有如rank等操作才將size域附加在節點中

插入刪除的均攤時間複雜度為\(\ord{logN}\),相較之下朝鮮樹只是他的劣質仿冒品,其複雜度證明請參考此論文

以下為模板:

這裡也提供不需要記錄節點大小(size)的平衡方式,相對的一些需要用到附加size域的函數將不能被使用,但插入刪除的效率不變


如果編譯發現沒有__lg()這個函數的話,請在程式碼開頭附上這份code:

2015年2月18日 星期三

[ korea tree ] 朝鮮樹

某天albus YY出來了一個沒有旋轉操作的平衡樹,由於albus的真名(华中科技大学附属中学 金正中)聽起來很像朝鮮主席,所以就叫朝鮮樹了!

朝鮮樹是一種不需旋轉的 自平衡二元搜尋樹,利用當深度大於max_deep(通常取sqrt(N))時暴力重建的方式讓平均時間為\(\ord{N*sqrt(N)}\),是一種很糟糕的平衡樹,但是我們還是要理解他,因為這樣暴力重建的概念會在其他樹上用到。
若題目的要求數據量<=500000時可以使用

所有操作都與本篇其他樹差不多只多了個rebuild函數,它會暴力將整顆樹重建成深度logN的平衡樹

對於重建的部分則使用了拍扁重建法,將樹先拍扁成鍊表後重建,只需要花費\(\ord 1\)的空間複雜度

以下提供模板:

2015年2月17日 星期二

[ Splay Tree ] 伸展樹模板

最近研究了伸展樹,它可以在均攤\(\ord{logN}\)的時間完成伸展操作,所謂的伸展操作就是將某個節點旋轉(rotate)到根(root)的過程,因為我們大部分在搜尋資料時,常常都只會用到特定的資料,其他大多數的資料是較少被搜尋的,因此將常被搜尋的資料靠近根是很好的策略,伸展樹由此被發明。
因為伸展樹可以分裂合併,所以可以取代分裂合併式treap或是分裂合併式randomize binary tree的功能,可以在競賽中被使用,而普通的伸展樹效率不高,故本文只介紹作區間處理的伸展樹
之後的link-cut tree會用到他,所以必須要能理解
例題: UVA 11922

定義伸展樹節點:(T為資料型態)

初始化時nil的l,r要指向自己

旋轉(跟其他樹差不多)
d=0左旋,1右旋

接下來是最重要的伸展操作
這是按劉汝佳在橘色那本書的寫法實現的
主要是將第k個節點伸展到root的過程
注意!! k必須大於0

有了splay操作,接下來是分裂&合併

當我們要維護一個區間1~n時,可以建立0~n的splay tree,0是廢棄節點,較為方便使用

最後提供新增節點的方法:

這樣所有的操作就齊全了
剩下的一些懶惰標記跟treap一樣,可以做區間翻轉和線段樹的功能
但是請小心指標的使用
(nil為衛兵指標,方便用來編輯,若不想用可以將程式碼略為修改)