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
相关话题
怎么证明每个位上的数字之和可以被3整除的数可以被3整除？将并行计算纳入算法竞赛，是否合适？
正负样本极不平衡的问题？
怎样实现浮点数除以一个数再乘以这个数结果等于原值?
如何学习数据结构？
为什么根据数组下标获取数据时间是一样的，难道下标不用寻址吗？
将并行计算纳入算法竞赛，是否合适？
掷一枚不均匀的硬币，正面概率为0.7，反面的概率为0.3，如何最高效地获得一个概率为0.5的事件？
大学想参加竞赛锻炼自己但很不容易怎么办？
如何判断这两份代码的时间复杂度？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
「贪心算法」的算法思路是什么，它存在什么缺陷？学习算法有什么入门级的书 ? 或者学习资料。(英语不太好)
报了蓝桥杯比赛，几乎零基础，如何准备，请大牛指导一下。谢谢？
如何评价 2021 年 ICPC 银川赛区？
如何看待noip吧疑似被卖？
如何看待 2022 年秋招算法岗人间地狱？
将并行计算纳入算法竞赛，是否合适？
算法研究属于数学专业还是计算机专业？
将并行计算纳入算法竞赛，是否合适？
谷歌翻译这几个月的进化速度突然加快是什么原因？
为什么根据数组下标获取数据时间是一样的，难道下标不用寻址吗？
怎样衡量一个机器学习工程师对算法的掌握程度？
奥赛生做高考题是种怎样的体验？
如何看待关于“数据结构与算法基础”的重要性？
是否存在一个函数，使得它的逆运算是容易求的，而它的逆运算的逆运算是难求的？
哪位大佬能来个骨灰级的红黑树讲解啊？
如何看待两次 IOI 金牌，一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师？
信息学竞赛算是边缘竞赛吗？
如何看待淘宝、微信、抖音推出算法关闭键？会带来哪些影响？还有哪些问题值得关注？
参加ICPC国际编程竞赛的大学生到底有多厉害，在校生该如何准备？
刷完算法导论和leetcode，能找到什么水平的工作？
从一读到一亿需要读多少个汉字？
未来会不会有一种方式，可以使一部蓝光电影压缩到几Mb甚至几Kb？
你在生活中用过最高级的算法知识是什么？
程序员应该如何学习算法？
如何看待关于“数据结构与算法基础”的重要性？
怎样将一个24的n次方复杂度的计算优化?
你靠哪些讲解学会了曾经怎么也学不会的算法？
智能座舱的算法包括哪些方面？
如何分配砝码使天平尽可能平衡？