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
相关话题
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？计算器或计算机如何进行比较复杂的数学计算？
计算机行业是不是自砸饭碗的行业？
非高中oi选手在清华计算机系就读是什么体验？
EM算法存在的意义是什么？
链表求交集，从链表头删去一长串而非一个节点？（已解决）?
有哪些令人拍案叫绝的算法？
如何分配砝码使天平尽可能平衡？
大家都见过哪些让你虎躯一震的代码？
你在生活中用过最高级的算法知识是什么？
前一个讨论
年薪三十万的码农不如一个省委办公厅公务员吗？
相关的话题
在一段高速公路上，30分钟之内见到汽车经过的概率是95%，那么，在10分钟内见到汽车经过的概率是多少？Minecraft 的地形生成算法是什么？
有哪些算法惊艳到了你？
有哪些算法或数据结构是ACM大牛们在比赛中创造出来的？
如何看待王思聪开始第二波抽奖，这轮抽奖结果的性别比是否会发生明显的变化？
正负样本极不平衡的问题？
刷完 LeetCode 是什么水平？能拿到什么水平的 offer？
哪本《数据结构与算法》最好？
有哪些解决完之后让你拍案叫绝的算法问题？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
如何激怒一位计算机科学爱好者？
有没有能向玩家保证服务器发牌时没有作弊的牌类游戏发牌算法？
如何系统学习机器学习？
如何判断这两份代码的时间复杂度？
单链表的头结点问题？
什么是递归？
沃罗诺伊图（Voronoi Diagram，也称作Dirichlet tessellation，狄利克雷镶嵌 ）是怎样的？
你写过什么有趣的程序？
对于任意既约分数，都可以分解成有限个不同奇数的倒数和吗？
哪位大佬能来个骨灰级的红黑树讲解啊？
如何看待王思聪开始第二波抽奖，这轮抽奖结果的性别比是否会发生明显的变化？
为什么下面程序递归计算斐波那契数列java比c++要快？
大公司笔试面试有哪些经典算法题目？
人工智能领域有哪些精妙的数学原理？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
一道程序员面试题？
如何看待O(n log n)时间的整数乘法算法?
红黑树的实现可以有多精简（各种语言随意）？
五子棋先下的一定赢吗？如何证明？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？