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
相关话题
如何评价教育部发文：AI、算法等2018年进入全国高中课程？《阮一峰版快速排序完全是错的》一文是否存在事实错误？
什么是 hash？
TikTok、抖音为什会成功，以至于微信、Google、Facebook 等大厂在短视频领域都折戟？
有一个三位数密码锁，如果输入的三位密码有1位是正确的，就会嘀一声响，请问最少要输入几次才一定能开锁？
如何看待 2020 届校招算法工程师岗位求职人数远大于招聘岗位的现象？
如何理解动态规划？
比特币的算法到底在算什么？
如何看待语音合成等 AI 算法、无人机等被列入限制出口技术目录？
你写过哪些比较酷的十行以内的 Matlab 代码？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
A*寻路是一种广度优先搜索？花一晚上也无法理解非递归遍历二叉树，我该继续学下去吗？
内存为啥要分堆栈在编程里，要是全部只用堆或者全部只用栈，行不行？
内存为啥要分堆栈在编程里，要是全部只用堆或者全部只用栈，行不行？
怎样实现浮点数除以一个数再乘以这个数结果等于原值?
有哪些令人拍案叫绝的算法？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
如何评价2021CCPC广东省赛(GDCPC-2021)？
平滑的战争迷雾效果是如何实现的？
军事级加密算法有哪些？
类似微博的 feed 热度算法如何计算？
假如我知道了抽卡游戏的随机数生成算法源码，是否能成为欧皇？
如何看待 2022 年秋招算法岗竞争如此激烈？
EM算法存在的意义是什么？
有没有必要把机器学习算法自己实现一遍？
你在写程序的时候经历过哪些有趣的事？
EM算法存在的意义是什么？
如何用简单易懂的例子解释隐马尔可夫模型？
为什么算法时间复杂度没有三角函数级别？
有哪些解决完之后让你拍案叫绝的算法问题？
Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异？
为什么说 MD5 是不可逆的？
量子计算机的出现会给实际生活带来怎样的改变？
智能座舱的算法包括哪些方面？
数字图像处理的工作是用传统算法更多还是用深度学习更多?
如何评价清华大学文素中心的老师认为「外语系学生参与科研的经历疑似是抄袭」的想法？
[题]两个数的最小公倍数是36，最大公因数是6，这两个数可能是多少？
利用无理数压缩数据是否可行？
如何评价各种关联因素分析算法,尤其是在算法效果对比方面?
可以利用抄代码来同时记忆算法与练英文书法吗？