Size Balanced Tree 真的是國內 ACM 選手陳啟峰的發明嗎？

01-19

偶然看到這個帖子，我來回答一下。

Size Balanced Tree (SBT)是我高中時寫的一篇集訓隊論文。有興趣的讀者可以看看我以前整理的SBT資料（從 http://www.stanford.edu/~cqf/SBT.zip 下載）。

首先澄清一點，SBT跟演算法導論裡面的Weight-balanced Tree (WBT) 有所不同。WBT維護的是子樹與兒子的關係，SBT維護的是子樹與侄子（兄弟的兒子）的關係。

從理論上來講，SBT和其他流行的平衡樹在攤平時間複雜度上沒有區別。

從實用角度來說，SBT在某些方面可能會超越其他平衡樹。在SBT的左/右旋轉過程中，所有節點的平均深度在下降，那麼查詢操作的期望深度也在降低（如果一個節點在深度d，那麼我們只需要走d步）。當查詢操作比較多的時候，SBT會有優勢。另外，SBT保存的子樹大小可以用來查詢第k大，而AVL，Treap，紅黑樹存儲的額外信息不能用來查詢第k大。

有沒有哪個演算法或數據結構是ACM大牛們在比賽中創造出來的？ - 編程

算是一種變體...

用著方便

release的時候跑不過map

具體到 Size Balanced Tree 也許是他的發明。但沒多大意義。

這應該算是一種 balanced binary tree，雖然他 balanced 是 size 而非 depth，但使用上沒什麼區別。這個結構的複雜度相比 balanced binary tree 也沒有提高。

balanced binary tree 中性能好的 Red–black tree 是 1972 年的發明；AVL 是 1962 年發明的；「最好寫」的 splay tree 是 1985 年發明的。我不知道 Size Balanced Tree 是啥時候，但我不認為它能有啥優勢。

講道理，所謂的Size Balanced Tree就是AVL的一個變體

AVL是用height平衡，SBT是用weight平衡

然而AVL最大的優勢就是她的height平衡使得平均深度相當優秀

而且。。。

那個論文裡面說，SBT跑得比Red Black Tree快

我就呵呵了，還專門測了一下，結果SBT被RBT吊著打

所以說，不要總想著發明一個大平衡樹，就把RBT批判一番

總結：

1.SBT是AVL的變體，不能完全說是陳啟峰發明的吧

2.SBT速度比treap還慢點，吊打紅黑樹什麼的實屬扯淡

3.SBT代碼挺長的，不算好寫

4.SBT能不能支持split merge呢。。個人認為還是可以的，但是似乎沒什麼人研究這方面的東西，所以暫且可以算是功能受限

總而言之基本上沒人用這玩意