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
相关话题
如何看待两次 IOI 金牌，一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师？戴克斯特拉算法（Dijkstra）的本质是贪心，还是动态规划？
一个程序员的水平能差到什么程度?
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
请问有哪些最优化算法可以做全局优化？
为什么技术主管跟我说程序员学算法不是最重要的，从工作项目中学习实际才是最重要的？
如何评价 DeepMind 公布的可生成算法竞赛解题代码的 AlphaCode？
DeepMind 再登 Nature，用 AI 破译古希腊文字，该成果会对人类历史研究带来什么影响？
为什么说程序员要贷款买房之前最好先学好数据结构和算法？
奥赛生做高考题是种怎样的体验？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
偏序性质的有向无环图的最大独立集如何求解?什么才算是真正的编程能力？
程序员必须掌握哪些算法？
很多高效排序算法的代价是 nlogn，难道这是排序算法的极限了吗？
如何看待三星Galaxy note10 5G DxO摄像头评测得分113分超华为P30 Pro？
程序员不需要知道太多数学，你认同吗？
有没有手算根号pi的方法？
有什么在线的编程游戏？
「C++ 早就过时了，大部分写工程不用 C++，学习这个语言只是为了竞赛」的观点是否正确？
参加 ACM-ICPC World Final 是怎样一种体验？
有哪些数学定理或者数学知识惊呆了你？
N个互异数随机组成的数组的逆序数的分布公式是什么？
什么是 hash？
可以用ACM/ICPC竞赛成绩来判定一个高校的计算机专业水准吗?
为什么很多大牛在写题的时候要加一堆宏？
你为什么要学算法？
正负样本极不平衡的问题？
卡尔曼滤波器是如何运用于多传感器融合的？
假如我知道了抽卡游戏的随机数生成算法源码，是否能成为欧皇？
机器学习到底是什么，如何使用这项技术？
中国目前的人工智能在全球处于什么水平？
中国目前的人工智能在全球处于什么水平？
在信息学竞赛中，你见过哪些"这都能AC!?"的题?
100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？
很多高效排序算法的代价是 nlogn，难道这是排序算法的极限了吗？
一个关于拓扑排序的扩展问题，可以做到的最优复杂度是？
蒙特卡罗算法是什么？
学习算法有什么入门级的书 ? 或者学习资料。(英语不太好)
刷完 LeetCode 是什么水平？能拿到什么水平的 offer？
最快的 atoi、atof 实现是什么样的？