<li id="smart-nav-recent" class="nav-section"><div class="nav-section-header"><a href="javascript:vold(0)">Article Nav</a></div><ul><li><a href="#article_nav-0" title="性质">性质</a></li> <li><a href="#article_nav-1" title="旋转">旋转</a></li> <li><a href="#article_nav-2" title="保持性质(Maintain)">保持性质(Maintain)</a></li> <li><a href="#respond">发表评论</a></li></ul></li>

。。按惯例笔记贴都是摘抄、转载的……TAT看了半天貌似还是不会写的样子……滚回去复习主席树了

Via NOCOW http://www.nocow.cn/index.php/Size_Balanced_Tree

Size Balanced Tree(SBT)是一种平衡二叉查找树。它的论文由中国广东中山纪念中学的陈启峰于2006年底完成，并在Winter Camp 2007中发表。由于SBT的拼写很容易找到中文谐音，它常被中国的OIer们戏称为“傻X树”、“Super BT”等。但它的性能并不SB，编写起来也并不BT。恰恰相反，SBT易于实现，且据陈启峰论文中所言，“这是目前为止速度最快的高级二叉搜索树”。它能在O(logn)的时间内完成所有BST的相关操作。而且由于SBT赖以保持平衡的是Size域而不是其他“无用”的域，它可以很方便地实现动态顺序统计中的select和rank。

性质

Size Balanced Tree（SBT）是一种通过大小（Size）域来保持平衡的二叉搜索树，它也因此得名。它总是满足：
对于SBT的每一个结点 t：

1. 性质(a) s[right[t] ]≥s[left[left[t]]]，s[right[left[t]]]
2. 性质(b) s[left[t] ]≥s[right[right[t]]]，s[left[right[t]]]

即每棵子树的大小不小于其兄弟的子树大小。

 

 

 

 

如图（圈代表结点，三角代表SBT，下同）：

 

 

 

 

1. s[R] ≥ s[A]，s[B]
2. s[L] ≥ s[C]，s[D]

旋转

SBT的旋转（Rotations）与其他许多高级BST相同。它是下面提到的Maintain操作的基础。

 

 

保持性质(Maintain)

当我们插入或删除一个结点后，SBT的大小就发生了改变。这种改变有可能导致性质(a)或(b)被破坏。这时，我们需要用Maintain操作来修复这棵树。Maintain操作是SBT中最具活力的一个独特过程；Maintain(T)用于修复以T为根的 SBT。调用Maintain(T)的前提条件是T的子树都已经是SBT了。
我们需要讨论的有4种情况。由于性质a和性质b是对称的，所以我们仅仅详细的讨论性质a。

1. 第一种情况：s[left[left[t]]>s[right[t]]如图3，执行完Insert(left[t],v)后发生S[A]>S[R]，我们可以执行以下的指令来修复SBT：
   1. 首先执行Right-Ratote(t)，这个操作让图3变成图4；
   2. 在这之后，有时候这棵树还仍然不是一棵SBT，因为 s[C]>s[B] 或者 s[D]>s[B] 也是可能发生的。所以就有必要继续调用Maintain(T)。
   3. 结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(L)。
2. 第二种情况：s[right[left[t]]>s[right[t]]在执行完Insert(left[t],v)后发生s[B]>s[R]，如图5，这种调整要比情况1复杂一些。我们可以执行下面的操作来修复：
   1. 在执行完Left-Ratote(L)后，图5就会变成下面图6那样了。
   2. 然后执行Right-Ratote(T)，最后的结果就会由图6转变成为下面的图7。
   3. 在第1步和第2步过后，整棵树就变得非常不可预料了。万幸的是，在图7中，子树A、E、F和R仍就是SBT，所以我们可以调用Maintain(L)和Maintain(T)来修复结点B的子树。
   4. 在第3步之后，子树都已经是SBT了，但是在结点B上还可能不满足性质a或性质b，因此我们需要再一次调用Maintain(B)。
3. 第三种情况：s[right[right[t]]>s[left[t]]
   与情况1对称。
4. 第四种情况：s[left[right[t]]>s[left[t]]
   与情况2对称。

通过前面的分析，很容易写出一个普通的Maintain。

前面的标准过程的伪代码有一点复杂和缓慢。通常我们可以保证性质a和性质b的满足，因此我们只需要检查情况1和情况2或者情况3和情况4，这样可以提高速度。所以在那种情况下，我们需要增加一个布尔（boolean）型变量：flag，来避免毫无意义的判断。如果flag是false，那么检查情况1和情况2；否则检查情况3和情况4。

为什么Maintain(left[t],true)和Maintain(right[t],false)被省略了呢？

……且听下回分解

[Dr.Lib]Note:Data Structures – Size Balanced Tree – I by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.