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
相关话题
在 ACM-ICPC 中获得很好成绩的人，现在都在干什么？腾讯面试题，如何寻找一个数组里面唯一不重复的元素?要求时间复杂度o（n）和空间复杂度o（1）?
如何看待两次 IOI 金牌，一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师？
哪本《数据结构与算法》最好？
机器学习到底是什么，如何使用这项技术？
能解释下怎么从这个有向图生成如图的集合链？（数字电路并行全入度拓扑排序优化算法）？
为什么英国顶尖大学在acm icpc表现不佳？
红黑树的实现可以有多精简（各种语言随意）？
如何通俗的解释模糊神经网络？
有没有手算根号pi的方法？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
竞技编程是否属于电子竞技？请教拓扑排序中的一点疑问？
你靠哪些讲解学会了曾经怎么也学不会的算法？
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
军事级加密算法有哪些？
100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？
《阮一峰版快速排序完全是错的》一文是否存在事实错误？
c中struct 为什么可以在数据结构这样用？
如何看待「原谅宝」？
负数与负数相乘为什么会得正？
感觉算法在程序员中快被吹上天了，如果只是搞编程的话，是不是没必要死磕算法？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
如何面对算法竞赛的焦虑？
五子棋先下的一定赢吗？如何证明？
你为什么要学算法？
干支纪年法的算法是什么？
量子计算机的出现会给实际生活带来怎样的改变？
为什么很多程序无法计算负数的立方根？
为什么英国顶尖大学在acm icpc表现不佳？
一道阿里笔试题，思路应该是怎样？
如何激怒一位计算机科学爱好者？
最快的 atoi、atof 实现是什么样的？
有没有大佬可以详细的讲讲链表？
要是往马斯克嵌在猪脑袋里面的芯片里写进去“猪的生命也是命”。猪会不会不让人类吃他们的肉了呢？ ?
[题]两个数的最小公倍数是36，最大公因数是6，这两个数可能是多少？
蒙特卡罗算法是什么？
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
算法源于大数据，而大数据源于我们每一个人，那我们是不是应该拥有主导数据的权利？
面试题:一个长度为n的数组，其中数组中每个元素的值都不大于n，如何用O(n)的算法判断数组中是否存在重复元素?
军事级加密算法有哪些？