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
相关话题
如何编程判断一个数是否是质数？你为什么要学算法？
智能座舱的算法包括哪些方面？
为什么 360 面试官说 Trie 树没用？
C++中开多个数组和用struct封装起来哪个速度更快？
链表和数组的插入删除时间复杂度都是o(n)，为什么教材网络上说链表效率高？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
感觉算法在程序员中快被吹上天了，如果只是搞编程的话，是不是没必要死磕算法？
如何看待 2021 年图灵奖授予美国计算机科学家 Jack J. Dongarra?
如何看待CCF关于举办首届NOI女生竞赛的通知？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
求十亿内所有质数的和，怎么做最快?什么才算是真正的编程能力？
为什么很多程序无法计算负数的立方根？
一道阿里笔试题，思路应该是怎样？
python怎么去掉最大值和最小值，怎么找到最大值与最小值，去掉最大值最小值比如下面这道题?
如何简单形象又有趣地讲解神经网络是什么？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
如何评价Google 在TensorFlow 中引入的bfloat16 数据类型？
为什么C#的.NET库不默认提供「优先队列」容器？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
怎样衡量一个机器学习工程师对算法的掌握程度？
你写过什么有趣的程序？
如何分配砝码使天平尽可能平衡？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
高斯模糊的原理是什么，怎样在界面中实现？
任何密码都可以用穷举推算出来，只是时间问题。如果是这样的话，那不是很不安全？
有哪些解决完之后让你拍案叫绝的算法问题？
单链表的头结点问题？
刚进算法团队，大牛们讨论高深的cv术语和算法，如何才能听懂？
奥赛生做高考题是种怎样的体验？
沃罗诺伊图（Voronoi Diagram，也称作Dirichlet tessellation，狄利克雷镶嵌 ）是怎样的？
算法工程师如何应对做算法策略的不确定性；比如没效果，这时绩效怎么保证？
算法工程师如何应对做算法策略的不确定性；比如没效果，这时绩效怎么保证？
如何看待滴滴章文嵩称，滴滴面临的问题比 AlphaGo 复杂 100 倍？
内存为啥要分堆栈在编程里，要是全部只用堆或者全部只用栈，行不行？
二分查找有几种写法？它们的区别是什么？
程序员必须掌握哪些算法？
Matlab中的conv函数与卷积公式是什么关系呢？
可达矩阵算法的原理是什么？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？