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
相关话题
如何评价百度自动驾驶 ApolloAuto 在 Github 上发布的代码？算法A时间复杂度O(n²)，算法B时间复杂度为O(n³)，为什么选择算法B而不选算法A的6个理由?
你写过哪些比较酷的十行以内的 Matlab 代码？
为什么很多大牛在写题的时候要加一堆宏？
有没有大佬可以详细的讲讲链表？
有哪些令人拍案叫绝的算法？
如何直观地解释 backpropagation 算法？
数字图像处理的工作是用传统算法更多还是用深度学习更多?
如何通俗地讲解 viterbi 算法？
如何通俗的解释模糊神经网络？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
你在生活中用过最高端的数学知识是什么？土木和机器学习/深度学习/算法的交叉岗位在哪里找呀？ 在哪找都找不到招聘公司?
可以用ACM/ICPC竞赛成绩来判定一个高校的计算机专业水准吗?
非CS背景，如何快速上手机器学习？
刚进算法团队，大牛们讨论高深的 cv 术语和算法，如何才能听懂？
利用无理数压缩数据是否可行？
美剧《硅谷》第三季第一集神秘代码写的是什么？
目标检测算法中Two-stage算法速度慢,到底在哪里?
Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异？
什么才算是真正的编程能力？
你认为最优美的数据结构是什么？
std::list::sort 用了什么算法？为什么速度这么快？
你靠哪些讲解学会了曾经怎么也学不会的算法？
在五大基础学科竞赛中你有哪些笑话和梗？
假如我知道了抽卡游戏的随机数生成算法源码，是否能成为欧皇？
用链表的目的是什么？省空间还是省时间？
在校生为了面试，有必要强行记住一些复杂算法如红黑树、KMP等的实现吗？
你认为最优美的数据结构是什么？
为什么英国顶尖大学在acm icpc表现不佳？
二分查找有几种写法？它们的区别是什么？
0基础开始,Leetcode200道题要多久左右?
如何直接跳出深层递归而不是一层一层跳出？
怎么证明每个位上的数字之和可以被3整除的数可以被3整除？
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
Minecraft 的地形生成算法是什么？
如何生成多个互不重叠的不同半径圆？
要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？
干支纪年法的算法是什么？
如何看待「原谅宝」？
可达矩阵算法的原理是什么？