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
相关话题
算法岗位真的需要顶会才能入场吗？从一读到一亿需要读多少个汉字？
请教拓扑排序中的一点疑问？
算法A时间复杂度O(n²)，算法B时间复杂度为O(n³)，为什么选择算法B而不选算法A的6个理由?
报了蓝桥杯比赛，几乎零基础，如何准备，请大牛指导一下。谢谢？
在电子游戏中99%的暴击率、1%的爆伤和1%的暴击率、99%的爆伤，两者谁带来的收益更高？
为什么 360 面试官说 Trie 树没用？
假如我知道了抽卡游戏的随机数生成算法源码，是否能成为欧皇？
什么才算是真正的编程能力？
在Auto ML的冲击下，ML算法人员是否会在前者成熟后失业的情况？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
1/3+1/6=计算机是如何得出0.5的?如何看待 2022 年秋招算法岗竞争如此激烈？
竞赛退役是种怎样的体验？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
为什么leetcode等OJ上Cpp的提交都以class solution而不是main函数作为入口?
如何评价各种关联因素分析算法,尤其是在算法效果对比方面?
为什么算法时间复杂度没有三角函数级别？
什么是递归？
使用数组可以表示哪些数据结构？
如何评价Google 在TensorFlow 中引入的bfloat16 数据类型？
如何对一个元素只有0和1的数组进行排序？
如何检验算法的正确性？
Alice 和 Bob 各有一个 0-9 的数，他们怎样能在不暴露自己数的前提下知道双方数字是否相同？
如何看待快手 CEO 宿华发文称，将用正确的价值观指导算法？
100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？
土木和机器学习/深度学习/算法的交叉岗位在哪里找呀？ 在哪找都找不到招聘公司?
2021-05-28：跳跃游戏 II。给定一个非负整数数组，你最初位于数组的第一个位...如何解答呢？
从一读到一亿需要读多少个汉字？
大林算法与PID算法有什么本质区别?
哪本《数据结构与算法》最好？
如何用一个1-8随机数生成器制作一个1-7随机数生成器？
如何评价一线大厂资深 APP 性能优化系列之异步优化与拓扑排序？
红黑树的实现可以有多精简（各种语言随意）？
算法A时间复杂度O(n²)，算法B时间复杂度为O(n³)，为什么选择算法B而不选算法A的6个理由?
红黑树的实现可以有多精简（各种语言随意）？
如何评价 DeepMind 公布的可生成算法竞赛解题代码的 AlphaCode？
有什么算法可以很快的找出所有完全对称日呢?
将并行计算纳入算法竞赛，是否合适？
uber优惠码的生成的规则是什么？
2021-05-28：跳跃游戏 II。给定一个非负整数数组，你最初位于数组的第一个位...如何解答呢？