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
相关话题
怎样实现浮点数除以一个数再乘以这个数结果等于原值?最快的 atoi、atof 实现是什么样的？
如何正确地用 Test Driven Development 实现算法？
竞赛退役是种怎样的体验？
为什么算法时间复杂度没有三角函数级别？
算法源于大数据，而大数据源于我们每一个人，那我们是不是应该拥有主导数据的权利？
如何看待关于“数据结构与算法基础”的重要性？
如何直接跳出深层递归而不是一层一层跳出？
python怎么去掉最大值和最小值，怎么找到最大值与最小值，去掉最大值最小值比如下面这道题?
哪些看似与图论无关的问题可用图论模型解决？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
C++中除以2和右移1有什么区别？在一段高速公路上，30分钟之内见到汽车经过的概率是95%，那么，在10分钟内见到汽车经过的概率是多少？
Apriori算法是什么？适用于什么情境？
Java对于int变量a，如何以最快速度计算34*a?
算法工程师如何应对做算法策略的不确定性；比如没效果，这时绩效怎么保证？
学物理为什么会觉得计算机很难？
NSA 在 RSA 加密算法中安置后门是怎么一回事，有何影响？
如何编程判断一个数是否是质数？
掷一枚不均匀的硬币，正面概率为0.7，反面的概率为0.3，如何最高效地获得一个概率为0.5的事件？
是否存在时间复杂度是O(tan N)的算法？
如何学习视频识别技术？
如何看待noip吧疑似被卖？
从算法的角度来看，Elsagate 事件暴露出了「自动推荐」的哪些问题，该如何规避？
任何密码都可以用穷举推算出来，只是时间问题。如果是这样的话，那不是很不安全？
目标检测算法中Two-stage算法速度慢,到底在哪里?
Linear least squares, Lasso,ridge regression有何本质区别？
竞技编程是否属于电子竞技？
100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？
数据结构与算法在工作的作用及其大学学到什么程度才算可以?
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
如何系统学习机器学习？
干支纪年法的算法是什么？
逃离丧尸包围的游戏，你能否逃生？
100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
电子设备（如电脑）内置时钟的算法是如何“分辨/度量”出一秒的长度的？
如何看待 2022 年秋招算法岗竞争如此激烈？
算法和算法策略是一个意思吗？
花一晚上也无法理解非递归遍历二叉树，我该继续学下去吗？
Linear least squares, Lasso,ridge regression有何本质区别？