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
相关话题
红黑树的实现可以有多精简（各种语言随意）？如何统计拓扑排序的个数？
五个囚犯先后从100颗绿豆中抓绿豆。抓得最多和最少的人将被处死，不能交流，可以摸出剩下绿豆的数量，谁的存活几率最大？
如何评价 2021 年 ICPC 银川赛区？
如何看待快手 CEO 宿华发文称，将用正确的价值观指导算法？
干支纪年法的算法是什么？
如何评价 2021 年 ICPC 银川赛区？
二分查找有几种写法？它们的区别是什么？
在知乎你见过哪些明显抱团点反对的问题，对社区有怎样的影响，你有什么好的建议？
有哪些数学定理或者数学知识惊呆了你？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
MD5哈希算法不可逆，但是网上有很多破译解密哈希密钥的网站，这些都是经过大数据堆积的吗？还是可以破解？Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
什么是机器学习？
平滑的战争迷雾效果是如何实现的？
如何理解算法时间复杂度的表示法，例如 O(n²)、O(n)、O(1)、O(nlogn) 等？
对于任意既约分数，都可以分解成有限个不同奇数的倒数和吗？
在Auto ML的冲击下，ML算法人员是否会在前者成熟后失业的情况？
如何看待关于“数据结构与算法基础”的重要性？
你认为最优美的数据结构是什么？
备战ACM，想问下有什么算法网课推荐吗?
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？
大公司笔试面试有哪些经典算法题目？
掷一枚不均匀的硬币，正面概率为0.7，反面的概率为0.3，如何最高效地获得一个概率为0.5的事件？
一个关于拓扑排序的扩展问题，可以做到的最优复杂度是？
在知乎你见过哪些明显抱团点反对的问题，对社区有怎样的影响，你有什么好的建议？
学习算法有什么入门级的书 ? 或者学习资料。(英语不太好)
python怎么去掉最大值和最小值，怎么找到最大值与最小值，去掉最大值最小值比如下面这道题?
你为什么要学算法？
如何练习编程的手速？
如何看待O(n log n)时间的整数乘法算法?
如何学习数据结构？
有没有大佬可以详细的讲讲链表？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
如果按国家分，哪个国家编程最厉害？有没有代表人物？
这张图中能数出多少个三角形？
nlp有哪些值得完整实现一遍的算法?
算法A时间复杂度O(n²)，算法B时间复杂度为O(n³)，为什么选择算法B而不选算法A的6个理由?
如何看待某选手以伪造性别为由举报跨性别全国青少年信息学奥林匹克联赛（NOIP）选手 NiroBC？
程序员不需要知道太多数学，你认同吗？
谁能最简单的详解椭圆曲线算法，secp256k1 是如何生成公钥和私钥的？