\( \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"}} \)
顯示具有 size balanced tree 標籤的文章。 顯示所有文章
顯示具有 size balanced tree 標籤的文章。 顯示所有文章

2015年1月9日 星期五

[ size balanced tree ] 節點大小平衡樹 ( 傻B樹 ) 複雜度證明(論文)

找了好久終於找到中国广东中山纪念中学的陈启峰size balanced tree的原作論文中文翻譯版
若需參考要者請點擊下載
原文連結
張貼者： 於 沒有留言:
標籤： , , ,

2015年1月1日 星期四

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

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


因為自己寫的速度有點慢，可以參考這邊一些大神寫的code
張貼者： 於 沒有留言:
標籤： , ,
訂閱： 文章 (Atom)