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
相关话题
一个程序员的水平能差到什么程度?利用无理数压缩数据是否可行？
美团公开外卖订单分配算法，详解算法如何判断一个骑手的时间宽裕程度和顺路程度，有哪些值得关注的信息？
用 C# 写个方法解析简单的 JSON 字符串有哪些思路？
算法工程师如何应对做算法策略的不确定性；比如没效果，这时绩效怎么保证？
刷完 LeetCode 是什么水平？能拿到什么水平的 offer？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
学数据结构有多痛苦？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
未来会不会有一种方式，可以使一部蓝光电影压缩到几Mb甚至几Kb？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
逃离丧尸包围的游戏，你能否逃生？在中国象棋中，最少用多少只马才能控制住整个棋盘？（马控棋盘）？
任何密码都可以用穷举推算出来，只是时间问题。如果是这样的话，那不是很不安全？
为什么在数学中，一些运算的逆运算比原运算难很多？
在校生为了面试，有必要强行记住一些复杂算法如红黑树、KMP等的实现吗？
N 个乒乓球中有一个和其他的质量不同，用天平最少几次一定能称出来？
如何评价 CCPC 2021 网络赛重赛？
C++中开多个数组和用struct封装起来哪个速度更快？
数据结构与算法中，树一般会应用在哪些方面？为什么？
构建进化树的意义是什么？除了看亲缘关系之外。
到了 2022 年，人工智能有哪些真正可落地的应用？
有没有能向玩家保证服务器发牌时没有作弊的牌类游戏发牌算法？
推荐系统有什么危害?
机器学习的算法和普通《算法导论》里的算法有什么本质上的异同？
Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异？
如何检验算法的正确性？
各种机器学习算法的应用场景分别是什么（比如朴素贝叶斯、决策树、K 近邻、SVM、逻辑回归最大熵模型）？
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
有什么在线的编程游戏？
任何密码都可以用穷举推算出来，只是时间问题。如果是这样的话，那不是很不安全？
高斯模糊的原理是什么，怎样在界面中实现？
如何理解算法时间复杂度的表示法，例如 O(n²)、O(n)、O(1)、O(nlogn) 等？
Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异？
哪些开发会用到微积分、离散数学、线性代数、概率论的知识？
怎样实现浮点数除以一个数再乘以这个数结果等于原值?
如何看待某选手以伪造性别为由举报跨性别全国青少年信息学奥林匹克联赛（NOIP）选手 NiroBC？
非计算机专业，想刷leetcode，请问在此之前需要做什么准备？
Alice 和 Bob 各有一个 0-9 的数，他们怎样能在不暴露自己数的前提下知道双方数字是否相同？
土木和机器学习/深度学习/算法的交叉岗位在哪里找呀？ 在哪找都找不到招聘公司?
Alice 和 Bob 各有一个 0-9 的数，他们怎样能在不暴露自己数的前提下知道双方数字是否相同？