\( \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年3月27日 星期五

[ basic operation of naive order statistic tree ] 樸素二元搜尋樹 名次樹的基本操作

一般的名次樹支援以下幾種操作:

1.插入
2.刪除
3.查找
4.求節點大小
5.求元素名次
6.求第k大
7.求前驅
8.求後繼

之前寫的模板已經有了前六種操作,因此我會在本模板中附上求前驅跟後繼的操作
前驅與後繼並不是名次樹才有的操作,在不記錄節點大小的情形下也能求得
關於求前驅跟後繼操作的說明可以參考 随机平衡二叉查找树Treap的分析与应用 這篇文章

以下提供模板:

2015年3月14日 星期六

[ AA tree ] AA樹

AA樹是紅黑樹的一種變種,是Arne Andersson教授在1993年年在他的論文"Balanced search trees made simple"中介紹,設計的目的是減少紅黑樹考慮的不同情況。區別於紅黑樹的是,AA樹的紅結點只能作為右葉子。另外AA樹為實現方便,不再使用紅黑兩種顏色,而是用level標記結點,結點中的level相當於紅黑樹中結點的黑高度。

其主要透過skew和split兩種旋轉來進行平衡的,插入時只能為紅節點,故會出現不符合其規定則進行平衡操作

若想進一步了解其平衡操作請參考維基百科
在實作中,skew為右璇,split為左旋。本模板以rotate(o,0)、rotate(o,1)代表

以下提供模板:

2015年3月13日 星期五

[ symmetric binary B-tree ( red black tree ) ] 對稱二叉B樹 ( 紅黑樹 )

紅黑樹是一種有最壞情況擔保的平衡樹,其插入最多會用到2個旋轉,刪除最多用到3個旋轉,其犧牲些許的平衡來加快插入刪除的速度,並有高度上h<=2*log(n+1)的保證。
故其插入刪除之常數會比較小,而查詢之常數會較大(相對於一般高度平衡樹),而一般的函式庫裡的"關聯數組"通常適用紅黑樹實做的
其平衡原因及方法請參考維基百科
因其操作複雜故不常在競賽中被使用,且刪除速度較size balanced tree慢約2倍

以下提供模板: