节点大小平衡树( Size Balanced Tree，缩写：SBT)是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构。它是由中国广东中山纪念中学的陈启峰发明的。陈启峰于2006年底完成论文《Size
Balanced Tree》，并在2007年的全国青少年信息学奥林匹克竞赛冬令营中发表。相比红黑树、AVL树等自平衡二叉查找树，SBT更易于实现。据陈启峰在论文中称，SBT是“目前为止速度最快的高级二叉搜索树”。SBT能在O(log
n)的时间内完成所有二叉搜索树(BST)的相关操作，而与普通二叉搜索树相比，SBT仅仅加入了简洁的核心操作Maintain。由于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操作的基础。

[编辑]左旋转

Left-Rotate (t)

1     k ← right[t]
2     right[t] ← left[k]
3     left[k] ← t
4     s[k] ← s[t]
5     s[t] ← s[left[t]] + s[right[t]] + 1
6     t ← k

[编辑]右旋转

Right-Rotate(t)

1     k ← left[t]
2     left[t] ← right[k]
3     right[k] ← t
4     s[k] ← s[t]
5     s[t] ← s[left[t]] + s[right[t]] + 1
6     t ← k

[编辑]保持性质(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（同图1）
   如图3，执行完Insert(left[t],v)后发生S[A]>S[R]，我们可以执行以下的指令来修复SBT：
   1. 首先执行Right-Ratote(t)，这个操作让图3变成图4；
      
      图4
   2. 在这之后，有时候这棵树还仍然不是一棵SBT，因为 或者 也是可能发生的。所以就有必要继续调用Maintian(t)。
   3. 结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(L)。
2. 第二种情况：s[right[left[t] ]>s[right[t] ]
   
   图5
   在执行完Insert(left[t],v)后发生s[B]>s[R]，如图5，这种调整要比情况1复杂一些。可以执行下面的操作来修复：
   1. 在执行完Left-Ratote(L)后，图5就会变成下面图6那样。
      
      图6
   2. 然后执行Right-Ratote(T)，最后的结果就会由图6转变成为下面的图7。
      
      图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。

Maintain (t)

01     If s[left[left[t]]>s[right[t]] then    //case1
02          Right-Rotate(t)
03          Maintain(right[t])
04          Maintain(t)
05          Exit
06     If s[right[left[t]]>s[right[t]] then   //case2
07          Left-Rotate(left[t])
08          Right-Rotate(t)
09          Maintain(left[t])
10          Maintain(right[t])
11          Maintain(t)
12          Exit
13     If s[right[right[t]]>s[left[t]] then   //case1
14          Left-Rotate(t)
15          Maintain(left[t])
16          Maintain(t)
17          Exit
18     If s[left[right[t]]>s[left[t]] then    //case2
19          Right-Rotate(right[t])
20          Left-Rotate(t)
21          Maintain(left[t])
22          Maintain(right[t])
23          Maintain(t)

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

Maintain (t,flag)

01     If flag=false then
02          If s[left[left[t]]>s[right[t]] then      //case1
03               Right-Rotate(t)
04          Else
05               If s[right[left[t]]>s[right[t]] then   //case2
06                    Left-Rotate(left[t])
07                     Right-Rotate(t)
08          Else                                   //needn’t repair
09               Exit
10     Else
11          If s[right[right[t]]>s[left[t]] then      //case1
12               Left-Rotate(t)
13          Else
14               If s[left[right[t]]>s[left[t]] then     //case2
15                    Right-Rotate(right[t])
16                    Left-Rotate(t)
17          Else                                    //needn’t repair
18               Exit
19     Maintain(left[t],false)                     //repair the left subtree
20     Maintain(right[t],true)                     //repair the right subtree
21     Maintain(t,false)                           //repair the whole tree
22     Maintain(t,true)                            //repair the whole tree

陈启峰在论文中说明了Maintain(left[t],true)和Maintain(right[t],false)被省略了后不影响效果。
论文中证明了每次Maintain后树的总深度总是递减；Maintain的平摊运行时间是O(1)。

[编辑]基本操作

[编辑]查找

SBT的查找操作与普通BST完全相同。下面的过程将返回指向目标节点的指针。

Search(t,k)

1     if x=NIL or k=key[t]
2        then return x
3     if k<key[x]
4        then return Search(left[x],k)
5        else return Search(right[x],k)

[编辑]取大/取小

由于SBT本身已经维护了size，因此这两项可用Select操作完成。

[编辑]后继

SBT的后继操作与普通BST完全相同。

[编辑]前趋

SBT的前趋操作与普通BST完全相同。它与上面的后继操作对称。

[编辑]插入

SBT的插入操作仅仅比普通BST的多出了一个Maintain操作，以及对s的简单维护（这在普通BST的动态顺序统计操作中也是必须的）。下面这个过程将一个节点v插入SBT中。

Insert (t,v)

1     If t=0 then
2        t ← v
3     Else
4        s[t] ← s[t]+1
5         If v<key[t] then
6              Insert(left[t],v)
7         Else
8              Insert(right[t],v)
9     Maintain(t,v≥key[t])

[编辑]删除

与普通维护size域的BST删除相同（无需Maintain）。

[编辑]动态顺序统计操作

由于SBT本来就是靠着size域来维持平衡的，当我们进行动态顺序统计操作时，我们就无需去“额外”维护一个size域来进行数据结构的扩张。这样，以下操作就与其他高级BST扩张后的动态顺序统计操作完全一样了。

[编辑]检索具有给定排序的元素

下面这个过程将返回一个指向以x为根的子树中包含第i小关键字的节点的指针。

Select(x,i)

1     r ← size[left[x]] + 1
2     if(i=r)
3          then return x
4     else if i<r
5          then return Select(left[x],r)
6     else return Select(right[x],i-r)

[编辑]求元素的秩

SBT的rank操作与普通BST完全相同。

[编辑]性能分析

SBT的高度是O(logn)，Maintain是O(1)，所有主要操作都是O(logn)。

[编辑]参考资料

1. 《Size Balanced Tree》，陈启峰，2007年
   [原文5.1节伪代码似乎有误]