Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？ 第1页
1
chen-qi-feng-17 网友的相关建议:
偶然看到这个帖子，我来回答一下。
Size Balanced Tree (SBT)是我高中时写的一篇集训队论文。有兴趣的读者可以看看我以前整理的SBT资料（从
http://www. stanford.edu/~cqf/SBT.z ip下载）。
首先澄清一点，SBT跟算法导论里面的Weight-balanced Tree (WBT) 有所不同。WBT维护的是子树与儿子的关系，SBT维护的是子树与侄子（兄弟的儿子）的关系。
从理论上来讲，SBT和其他流行的平衡树在摊平时间复杂度上没有区别。
从实用角度来说，SBT在某些方面可能会超越其他平衡树。在SBT的左/右旋转过程中，所有节点的平均深度在下降，那么查询操作的期望深度也在降低（如果一个节点在深度d，那么我们只需要走d步）。当查询操作比较多的时候，SBT会有优势。另外，SBT保存的子树大小可以用来查询第k大，而AVL，Treap，红黑树存储的额外信息不能用来查询第k大。
1
相关话题
C++中除以2和右移1有什么区别？为什么埃式筛法的时间复杂度是O(nloglogn)？
失传的缀数法最有可能是什么方法？
如何直接跳出深层递归而不是一层一层跳出？
如何学习视频识别技术？
N 个乒乓球中有一个和其他的质量不同，用天平最少几次一定能称出来？
花一晚上也无法理解非递归遍历二叉树，我该继续学下去吗？
算法和算法策略是一个意思吗？
世界上有哪些代码量很少，但很牛逼很经典的算法或项目案例？
感觉算法在程序员中快被吹上天了，如果只是搞编程的话，是不是没必要死磕算法？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
是否存在时间复杂度是O(tan N)的算法？哪本《数据结构与算法》最好？
在机器学习模型的训练期间，大概几十分钟到几小时不等，大家都会在等实验的时候做什么？
禁止使用sqrt等返回浮点数的函数，如何最高效的得到最小的不小于给定正整数的完全平方数？
要是往马斯克嵌在猪脑袋里面的芯片里写进去“猪的生命也是命”。猪会不会不让人类吃他们的肉了呢？ ?
网上常能见到的一段 JS 随机数生成算法如下，为什么用 9301, 49297, 233280 这三个数字做基数？
各种机器学习算法的应用场景分别是什么（比如朴素贝叶斯、决策树、K 近邻、SVM、逻辑回归最大熵模型）？
如何理解计算物理中的元胞链接列表（Cell Linked List）算法？
在编程中有没有巧妙运用数学知识解决过问题？
将并行计算纳入算法竞赛，是否合适？
nlp有哪些值得完整实现一遍的算法?
有哪些令人拍案叫绝的算法？
是否存在一个函数，使得它的逆运算是容易求的，而它的逆运算的逆运算是难求的？
如何看待CCF关于举办首届NOI女生竞赛的通知？
1/3+1/6=计算机是如何得出0.5的?
PRML为何是机器学习的经典书籍中的经典？
谷歌翻译这几个月的进化速度突然加快是什么原因？
如何检验算法的正确性？
五个囚犯先后从100颗绿豆中抓绿豆。抓得最多和最少的人将被处死，不能交流，可以摸出剩下绿豆的数量，谁的存活几率最大？
如何评价b站up主图灵的猫关于tiktok的视频？
Minecraft 的地形生成算法是什么？
IOI国际金牌是什么水平，在此之上更高的水平是什么样的？
Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异？
数据结构与算法在工作的作用及其大学学到什么程度才算可以?
一个N*N的矩阵，取值为0或1，有什么好的算法判断一行或一列全为1啊？
怎么证明每个位上的数字之和可以被3整除的数可以被3整除？
Linear least squares, Lasso,ridge regression有何本质区别？
如何把梯度传递过Argmax?
谁能最简单的详解椭圆曲线算法，secp256k1 是如何生成公钥和私钥的？
如何理解动态规划？