\( \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月13日 星期五

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

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

以下提供模板:

沒有留言:

張貼留言