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
相关话题
负数与负数相乘为什么会得正？在校生为了面试，有必要强行记住一些复杂算法如红黑树、KMP等的实现吗？
报了蓝桥杯比赛，几乎零基础，如何准备，请大牛指导一下。谢谢？
TikTok、抖音为什会成功，以至于微信、Google、Facebook 等大厂在短视频领域都折戟？
求十亿内所有质数的和，怎么做最快?
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
cpp是不是最方便研究算法的语言？
作为学数学的人，你有哪些用于「双十一」购物的方法？
如何把梯度传递过Argmax?
竞技编程是否属于电子竞技？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
有没有三维的数据结构？为什么下面程序递归计算斐波那契数列java比c++要快？
是否存在一个字符串，它的md5值是其自身？
你靠哪些讲解学会了曾经怎么也学不会的算法？
ACM 竞赛的题目在专业程序员眼中是怎样的水准？
算法A时间复杂度O(n²)，算法B时间复杂度为O(n³)，为什么选择算法B而不选算法A的6个理由?
什么是哈希洪水攻击（Hash-Flooding Attack）？
竞技编程是否属于电子竞技？
你们初刷leetcode时会怀疑自己的智商吗？
数据结构与算法在工作的作用及其大学学到什么程度才算可以?
《阮一峰版快速排序完全是错的》一文是否存在事实错误？
算法研究属于数学专业还是计算机专业？
如何看待网传字节跳动 28 岁图像算法工程师心梗猝死？还有 30 年房贷没还完，可以退房退款吗？
如何评价 DeepMind 公布的可生成算法竞赛解题代码的 AlphaCode？
「贪心算法」的算法思路是什么，它存在什么缺陷？
哪位大佬能来个骨灰级的红黑树讲解啊？
有没有手算根号pi的方法？
带一堆指针的链式结构怎么写才好？
面试题:一个长度为n的数组，其中数组中每个元素的值都不大于n，如何用O(n)的算法判断数组中是否存在重复元素?
1/3+1/6=计算机是如何得出0.5的?
如何面对算法竞赛的焦虑？
什么才算是真正的编程能力？
量子计算机的出现会给实际生活带来怎样的改变？
有什么理论复杂但是实现简单的算法？
如何学习视频识别技术？
你见过哪些神一样的优化操作？
普通人如何对抗算法，从而避免信息茧房？
为什么有人说弄懂了《算法导论》的 90%，就超越了 90%的程序员？
如何看待 NOIP2020 某选手通过修改输入文件获得了第三题的满分？
微信红包的随机算法是怎样实现的？