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
相关话题
如何评价Google 在TensorFlow 中引入的bfloat16 数据类型？计算机行业是不是自砸饭碗的行业？
在一个非常繁忙的十字路口，红绿灯坏了，请问无人驾驶汽车能顺利通过吗？
数学/算法：正方形内有5个点，为什么最近点对的距离小于边长？
单链表的头结点问题？
如何看待noip吧疑似被卖？
0x5f3759df这个快速开方中的常数的数学依据是什么？
如何练习编程的手速？
如何看待 2022 年秋招算法岗人间地狱？
谷歌翻译这几个月的进化速度突然加快是什么原因？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
戴克斯特拉算法（Dijkstra）的本质是贪心，还是动态规划？ACM 竞赛的题目在专业程序员眼中是怎样的水准？
开发人员如何构建自己的学习笔记系统？
怎样学好动态规划？
红黑树的实现可以有多精简（各种语言随意）？
腾讯面试题，如何寻找一个数组里面唯一不重复的元素?要求时间复杂度o（n）和空间复杂度o（1）?
可以用ACM/ICPC竞赛成绩来判定一个高校的计算机专业水准吗?
QR 二维码在不影响扫码的情况下，哪些部分可以删除？
军事级加密算法有哪些？
如何学习数据结构？
大二学生，计算机科学与技术专业，学到数据结构和组原有点心态爆炸了，看不懂敲不出代码，还有救吗 ？
公民身份号码有可能是素数吗？
在信息学竞赛中，你见过哪些"这都能AC!?"的题?
递归和循环相比耗费更多的空间，对于循环来说除了可以简化逻辑外还有什么优点吗？
有没有可能让计算机去理解代码，从而写代码？
面试提问2的10次方是多少是否合适?
如何证明快速排序法的平均复杂度为 O(nlogn)？
正负样本极不平衡的问题？
参加ICPC国际编程竞赛的大学生到底有多厉害，在校生该如何准备？
如何看待 2022 年秋招算法岗竞争如此激烈？
备战ACM，想问下有什么算法网课推荐吗?
一道程序员面试题？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
如何分配砝码使天平尽可能平衡？
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
如何看待O(n log n)时间的整数乘法算法?
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？
红黑树的实现可以有多精简（各种语言随意）？
从一读到一亿需要读多少个汉字？
你在生活中用过最高级的算法知识是什么？