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

[ size balanced tree ] 節點大小平衡樹 ( 傻B樹 )

它是由中国广东中山纪念中学的陈启峰發明的[已新增其中文論文連結]
跟一般的平衡樹一樣，靠左旋和右旋維持其平衡
他的精華來自於maintain函數
聽說是均攤\(\ord 1\)的，傳說中速度僅次於紅黑樹
coding複雜度跟Treap差不多，比AVL Tree好寫
平衡調件為: 每顆子樹的大小不小於其兄弟子樹的大小
我只提供模板，這裡有詳細的介紹


因為自己寫的速度有點慢，可以參考這邊一些大神寫的code
張貼者： 於
標籤： , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)