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
相关话题
N 个乒乓球中有一个和其他的质量不同，用天平最少几次一定能称出来？python怎么去掉最大值和最小值，怎么找到最大值与最小值，去掉最大值最小值比如下面这道题?
如何分配砝码使天平尽可能平衡？
0基础开始,Leetcode200道题要多久左右?
如何面对算法竞赛的焦虑？
Minecraft 的地形生成算法是什么？
备战ACM，想问下有什么算法网课推荐吗?
军事级加密算法有哪些？
微信红包的随机算法是怎样实现的？
有没有手算根号pi的方法？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
如何看待淘宝、微信、抖音推出算法关闭键？会带来哪些影响？还有哪些问题值得关注？电子设备（如电脑）内置时钟的算法是如何“分辨/度量”出一秒的长度的？
为什么埃式筛法的时间复杂度是O(nloglogn)？
如何理解动态规划？
如何简单形象又有趣地讲解神经网络是什么？
将并行计算纳入算法竞赛，是否合适？
李彦宏批评推荐式算法，你怎么看？
蒙特卡罗算法是什么？
哪本《数据结构与算法》最好？
如何评价各种关联因素分析算法,尤其是在算法效果对比方面?
奥赛生做高考题是种怎样的体验？
学了四年算法，码了五万行代码，但是大一期末C语言模拟及不了格怎么办？
为什么C#的.NET库不默认提供「优先队列」容器？
大林算法与PID算法有什么本质区别?
Auto X的自动驾驶技术用了什么技术？
经过足够长的时间， AlphaGo 的棋谱能收敛到一张上吗？
为什么有些算法工程师从来不谈业务，不谈解决问题，不谈价值挖掘，开口闭口就是算法模型，炼丹调参工程化？
怎样将一个24的n次方复杂度的计算优化?
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
MIT 猎豹机器人算法有多复杂？中国是否能研发出这种机器人？
程序员应该如何学习算法？
如何通俗地讲解 viterbi 算法？
算法岗位真的需要顶会才能入场吗？
微信红包的随机算法是怎样实现的？
递归的本质是什么？
如何系统学习机器学习？
为什么梯度下降能找到最小值？
为什么很多大牛在写题的时候要加一堆宏？
你认为最优美的数据结构是什么？
算法书如何选择？