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
相关话题
面试提问2的10次方是多少是否合适?人工智能领域有哪些精妙的数学原理？
请问有哪些最优化算法可以做全局优化？
NSA 在 RSA 加密算法中安置后门是怎么一回事，有何影响？
报了蓝桥杯比赛，几乎零基础，如何准备，请大牛指导一下。谢谢？
如何看待某选手以伪造性别为由举报跨性别全国青少年信息学奥林匹克联赛（NOIP）选手 NiroBC？
std::list::sort 用了什么算法？为什么速度这么快？
如何评价姜新文老师提出的NP=P这篇文章？
为什么leetcode等OJ上Cpp的提交都以class solution而不是main函数作为入口?
非计算机专业，想刷leetcode，请问在此之前需要做什么准备？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
如何高效地获得玩家排名？如何看待快手 CEO 宿华发文称，将用正确的价值观指导算法？
美团公开外卖订单分配算法，详解算法如何判断一个骑手的时间宽裕程度和顺路程度，有哪些值得关注的信息？
在一个非常繁忙的十字路口，红绿灯坏了，请问无人驾驶汽车能顺利通过吗？
是否存在时间复杂度是O(tan N)的算法？
算法和算法策略是一个意思吗？
为什么很多大牛在写题的时候要加一堆宏？
如何找到一个10项的非负整数数列，使该数列的任意不超过3项的和不重复，并使数列的最大项最小，并证明?
竞赛退役是种怎样的体验？
二分查找有几种写法？它们的区别是什么？
一个程序员的水平能差到什么程度?
如何直接跳出深层递归而不是一层一层跳出？
想学好计算机算法，是否需要重新学数学呢?
算法工程师如何应对做算法策略的不确定性；比如没效果，这时绩效怎么保证？
大二学生，计算机科学与技术专业，学到数据结构和组原有点心态爆炸了，看不懂敲不出代码，还有救吗 ？
平滑的战争迷雾效果是如何实现的？
使用数组可以表示哪些数据结构？
算法老师劝学生放弃学习 JavaScript，我该怎么办？
开发一个 App，利用 Bose 降噪耳机的原理实现其功能？
军事级加密算法有哪些？
为什么有人说弄懂了《算法导论》的 90%，就超越了 90%的程序员？
竞赛退役是种怎样的体验？
计算机视觉（CV）的算法有哪些，具体都有哪些特点？
《阮一峰版快速排序完全是错的》一文是否存在事实错误？
在编程中有没有巧妙运用数学知识解决过问题？
目标检测算法中Two-stage算法速度慢,到底在哪里?
怎样学好动态规划？
如何看待2021年秋招算法岗灰飞烟灭？
竞技编程是否属于电子竞技？
如何用一个1-8随机数生成器制作一个1-7随机数生成器？