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
相关话题
如何看待2021年秋招算法岗灰飞烟灭？为什么有人说弄懂了《算法导论》的 90%，就超越了 90%的程序员？
如何评价一线大厂资深 APP 性能优化系列之异步优化与拓扑排序？
算法老师劝学生放弃学习 JavaScript，我该怎么办？
你为什么要学算法？
有没有必要把机器学习算法自己实现一遍？
哪段代码最能代表程序员的暴力美学？
C++中开多个数组和用struct封装起来哪个速度更快？
刚进算法团队，大牛们讨论高深的cv术语和算法，如何才能听懂？
大一计算机专业不参加ACM就没前途吗？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
为什么梯度下降能找到最小值？请教拓扑排序中的一点疑问？
Algorithmic Game Theory 和经济学中的 Game Theory 相似度大吗？
能解释下怎么从这个有向图生成如图的集合链？（数字电路并行全入度拓扑排序优化算法）？
std::list::sort 用了什么算法？为什么速度这么快？
请问有哪些最优化算法可以做全局优化？
参加 ACM-ICPC World Final 是怎样一种体验？
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
为什么梯度下降能找到最小值？
内存为啥要分堆栈在编程里，要是全部只用堆或者全部只用栈，行不行？
这张算数入门图（一只兔子加一只兔子）里的题在算什么？
二分查找有几种写法？它们的区别是什么？
如何用简单易懂的例子解释隐马尔可夫模型？
学习算法有什么入门级的书 ? 或者学习资料。(英语不太好)
如何学习数据结构？
为什么同样是解决一个问题，别人就能想出算法，而我却绞尽脑汁，百般尝试也不得其法？
如何看待阿里 P8 加面 coding 环节，而 P7 却做不出头条算法题？
如果按国家分，哪个国家编程最厉害？有没有代表人物？
使用 open addressing 的 Hash 表载荷过高为什么会降低 CPU 的缓存命中率？
哪段代码最能代表程序员的暴力美学？
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
如何通俗的解释模糊神经网络？
如何看待O(n log n)时间的整数乘法算法?
怎样衡量一个机器学习工程师对算法的掌握程度？
二分查找有几种写法？它们的区别是什么？
nlp有哪些值得完整实现一遍的算法?
竞技编程是否属于电子竞技？
你为什么要学算法？
算法源于大数据，而大数据源于我们每一个人，那我们是不是应该拥有主导数据的权利？
你写过哪些比较酷的十行以内的 Matlab 代码？