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
相关话题
大公司笔试面试有哪些经典算法题目？开发一个 App，利用 Bose 降噪耳机的原理实现其功能？
如何计算一局三国杀所进行的回合数的数学期望？
MD5哈希算法不可逆，但是网上有很多破译解密哈希密钥的网站，这些都是经过大数据堆积的吗？还是可以破解？
计科和软工的区别？报哪个专业好些？
刷完算法导论和leetcode，能找到什么水平的工作？
数据结构与算法中，树一般会应用在哪些方面？为什么？
大一计算机专业不参加ACM就没前途吗？
2021-05-28：跳跃游戏 II。给定一个非负整数数组，你最初位于数组的第一个位...如何解答呢？
计算器或计算机如何进行比较复杂的数学计算？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
为什么得不到「自由意志」会让那么多人难以接受？程序员能 20 分钟徒手写出一个没 bug 的 KMP 算法吗？（可以调试）
如何分配砝码使天平尽可能平衡？
如果某一天证实随机数根本就不存在，会对生活的各个领域产生什么样的影响？
天天P图中我的小学生证件照功能怎么实现的？算法是什么样？
中宣部等五部门要求治理算法推荐，不给错误内容提供传播渠道，你认为目前算法推荐存在哪些问题？
为什么 360 面试官说 Trie 树没用？
有什么理论复杂但是实现简单的算法？
Matlab中的conv函数与卷积公式是什么关系呢？
土木和机器学习/深度学习/算法的交叉岗位在哪里找呀？ 在哪找都找不到招聘公司?
如何评价 2021 年 ICPC 银川赛区？
ICLR 2019 有什么值得关注的亮点？
有什么理论复杂但是实现简单的算法？
如何看待关于“数据结构与算法基础”的重要性？
链表和数组的插入删除时间复杂度都是o(n)，为什么教材网络上说链表效率高？
你在写程序的时候经历过哪些有趣的事？
计算复杂性理论是否具有足够的现实意义，如今有哪些比较「现实」的应用？
Linear least squares, Lasso,ridge regression有何本质区别？
如何评价姜新文老师提出的NP=P这篇文章？
从一读到一亿需要读多少个汉字？
如何看待 2020 届校招算法工程师岗位求职人数远大于招聘岗位的现象？
什么是哈希洪水攻击（Hash-Flooding Attack）？
构建进化树的意义是什么？除了看亲缘关系之外。
为什么埃式筛法的时间复杂度是O(nloglogn)？
为什么埃式筛法的时间复杂度是O(nloglogn)？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
量子计算机的出现会给实际生活带来怎样的改变？
为什么梯度下降能找到最小值？
能解释下怎么从这个有向图生成如图的集合链？（数字电路并行全入度拓扑排序优化算法）？
刷完 LeetCode 是什么水平？能拿到什么水平的 offer？