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
相关话题
数据结构与算法在工作的作用及其大学学到什么程度才算可以?程序员不需要知道太多数学，你认同吗？
参加 ACM-ICPC World Final 是怎样一种体验？
大林算法与PID算法有什么本质区别?
如何看待2021年秋招算法岗灰飞烟灭？
将并行计算纳入算法竞赛，是否合适？
C++中开多个数组和用struct封装起来哪个速度更快？
如何计算一局三国杀所进行的回合数的数学期望？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
有哪些手算对数的方法？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
有一个三位数密码锁，如果输入的三位密码有1位是正确的，就会嘀一声响，请问最少要输入几次才一定能开锁？是否存在一个字符串，它的md5值是其自身？
作为学数学的人，你有哪些用于「双十一」购物的方法？
奥赛生做高考题是种怎样的体验？
如何系统地学习算法？
中宣部等五部门要求治理算法推荐，不给错误内容提供传播渠道，你认为目前算法推荐存在哪些问题？
如何评价 DeepMind 公布的可生成算法竞赛解题代码的 AlphaCode？
如何看待语音合成等 AI 算法、无人机等被列入限制出口技术目录？
怎么证明每个位上的数字之和可以被3整除的数可以被3整除？
哪个高中竞赛性价比最高？
是否存在仅由1和2组成的长度为2^n的序列，可以做到在这个序列中取出所有含1和2的长度为n的序列？
如何高效地获得玩家排名？
QR 二维码在不影响扫码的情况下，哪些部分可以删除？
你写过什么有趣的程序？
从一读到一亿需要读多少个汉字？
Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异？
「C++ 早就过时了，大部分写工程不用 C++，学习这个语言只是为了竞赛」的观点是否正确？
如何看待两次 IOI 金牌，一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师？
数据结构与算法中，树一般会应用在哪些方面？为什么？
使用数组可以表示哪些数据结构？
负数与负数相乘为什么会得正？
为什么C#的.NET库不默认提供「优先队列」容器？
如何通俗地讲解 viterbi 算法？
苹果的 Differential Privacy 差分隐私技术是什么原理？
想在业余时间刷leetcode，配合什么书籍/课程/视频网站一起刷leetcode的效率最高？
ICLR 2019 有什么值得关注的亮点？
作为学数学的人，你有哪些用于「双十一」购物的方法？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
能否使用神经网络来判断奇偶数？
在校生为了面试，有必要强行记住一些复杂算法如红黑树、KMP等的实现吗？