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
相关话题
土木和机器学习/深度学习/算法的交叉岗位在哪里找呀？ 在哪找都找不到招聘公司?N 个乒乓球中有一个和其他的质量不同，用天平最少几次一定能称出来？
竞技编程是否属于电子竞技？
带一堆指针的链式结构怎么写才好？
程序员必须掌握哪些算法？
在五大基础学科竞赛中你有哪些笑话和梗？
如何评价清华大学文素中心的老师认为「外语系学生参与科研的经历疑似是抄袭」的想法？
如果按国家分，哪个国家编程最厉害？有没有代表人物？
高斯模糊的原理是什么，怎样在界面中实现？
怎样衡量一个机器学习工程师对算法的掌握程度？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
想学好计算机算法，是否需要重新学数学呢?如何评价 2021 年 ICPC 银川赛区？
什么是机器学习？
如何学习视频识别技术？
任何密码都可以用穷举推算出来，只是时间问题。如果是这样的话，那不是很不安全？
为什么 Google 翻译只重算法不重语言学的语法结构和规则？
红黑树的实现可以有多精简（各种语言随意）？
怎样衡量一个机器学习工程师对算法的掌握程度？
QR 二维码在不影响扫码的情况下，哪些部分可以删除？
如何利用群论的知识解决三阶魔方？
卡尔曼滤波器是如何运用于多传感器融合的？
为什么很多程序无法计算负数的立方根？
RSA的公钥和私钥到底哪个才是用来加密和哪个用来解密？
为什么现在有这么多人工智能无用论？
如何评价百度自动驾驶 ApolloAuto 在 Github 上发布的代码？
怎样学好动态规划？
如何理解动态规划？
如何用一个1-8随机数生成器制作一个1-7随机数生成器？
你认为最优美的数据结构是什么？
为什么梯度下降能找到最小值？
如何证明一个数 n 的因子之和是 O(n) 的？
掷一枚不均匀的硬币，正面概率为0.7，反面的概率为0.3，如何最高效地获得一个概率为0.5的事件？
你为什么要学算法？
如何看待「原谅宝」？
算法研究属于数学专业还是计算机专业？
机器学习到底是什么，如何使用这项技术？
有哪些见过的时间复杂度为无限大的算法？
为什么微软建议超过64字节不要使用结构？
算法老师劝学生放弃学习 JavaScript，我该怎么办？
怎样学好动态规划？