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
相关话题
在信息学竞赛中，你见过哪些"这都能AC!?"的题?IOI国际金牌是什么水平，在此之上更高的水平是什么样的？
对于任意既约分数，都可以分解成有限个不同奇数的倒数和吗？
NSA 在 RSA 加密算法中安置后门是怎么一回事，有何影响？
哪些开发会用到微积分、离散数学、线性代数、概率论的知识？
感觉算法在程序员中快被吹上天了，如果只是搞编程的话，是不是没必要死磕算法？
你写过什么有趣的程序？
为什么现在有这么多人工智能无用论？
ACM 竞赛的题目在专业程序员眼中是怎样的水准？
如何看待noip吧疑似被卖？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
参加 ACM-ICPC World Final 是怎样一种体验？机器学习里的 kernel 是指什么？
作为学数学的人，你有哪些用于「双十一」购物的方法？
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
程序员能 20 分钟徒手写出一个没 bug 的 KMP 算法吗？（可以调试）
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
请问《计算机网络》《操作系统》《 组成原理》《 数据库》 学习的先后顺序是怎么样的，怎样学好？
为什么C#的.NET库不默认提供「优先队列」容器？
Minecraft 的地形生成算法是什么？
目标检测算法中Two-stage算法速度慢,到底在哪里?
二分查找有几种写法？它们的区别是什么？
程序员不需要知道太多数学，你认同吗？
如何直接跳出深层递归而不是一层一层跳出？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
你为什么要学算法？
从算法的角度来看，Elsagate 事件暴露出了「自动推荐」的哪些问题，该如何规避？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
只需4组数据，还原你的购物模式，具体算法是怎么实现的？
竞技编程是否属于电子竞技？
什么是递归？
如何看待 2022 年秋招算法岗人间地狱？
大学想参加竞赛锻炼自己但很不容易怎么办？
算法工程师如何应对做算法策略的不确定性；比如没效果，这时绩效怎么保证？
在Auto ML的冲击下，ML算法人员是否会在前者成熟后失业的情况？
RSA的公钥和私钥到底哪个才是用来加密和哪个用来解密？
你为什么要学算法？
如何看待 2021 年图灵奖授予美国计算机科学家 Jack J. Dongarra?
如何分配砝码使天平尽可能平衡？
如何评价姜新文老师提出的NP=P这篇文章？
为什么有些算法工程师从来不谈业务，不谈解决问题，不谈价值挖掘，开口闭口就是算法模型，炼丹调参工程化？