Size Balanced Tree（SBT）-白红宇

Size Balanced Tree（SBT）

阅读量：4128 次

发布时间：2019-05-25

本文共 7413 字，大约阅读时间需要 24 分钟。

转载：http://www.nocow.cn/index.php/Size_Balanced_Tree

性质

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

对于SBT的每一个结点 t：

性质(a) s[right[t] ]≥s[left[left[t]]]，s[right[left[t]]]

性质(b) s[left[t] ]≥s[right[right[t]]]，s[left[right[t]]]

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

图1

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

s[R] ≥ s[A]，s[B]

s[L] ≥ s[C]，s[D]

[] 旋转

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

图2

[] 左旋转

Left-Rotate (t)1     k ← right[t]2     right[t] ← left[k]3     left[k] ← t4     s[k] ← s[t]5     s[t] ← s[left[t]] + s[right[t]] + 16     t ← k

[] 右旋转

Right-Rotate(t)1     k ← left[t]2     left[t] ← right[k]3     right[k] ← t4     s[k] ← s[t]5     s[t] ← s[left[t]] + s[right[t]] + 16     t ← k

[] 保持性质(Maintain)

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

我们需要讨论的有4种情况。由于性质a和性质b是对称的，所以我们仅仅详细的讨论性质a。

第一种情况：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，因为 s[C]>s[B] 或者 s[D]>s[B] 也是可能发生的。所以就有必要继续调用Maintain(T)。
3. 结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(L)。

第二种情况：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)。

第三种情况：s[right[right[t]]>s[left[t]]
与情况1对称。

第四种情况：s[left[right[t]]>s[left[t]]
与情况2对称。

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

Maintain (t)01     If s[left[left[t]]>s[right[t]] then    //case102          Right-Rotate(t)03          Maintain(right[t])04          Maintain(t)05          Exit06     If s[left[right[t]]>s[right[t]] then   //case207          Left-Rotate(left[t])08          Right-Rotate(t)09          Maintain(left[t])10          Maintain(right[t])11          Maintain(t)12          Exit13     If s[right[right[t]]>s[left[t]] then   //case1'14          Left-Rotate(t)15          Maintain(left[t])16          Maintain(t)17          Exit18     If s[right[left[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，这样可以提高速度。所以在那种情况下，我们需要增加一个布尔（boolean）型变量：flag，来避免毫无意义的判断。如果flag是false，那么检查情况1和情况2；否则检查情况3和情况4。

Maintain (t,flag)01     If flag=false then02          If s[left[left[t]]>s[right[t]] then      //case103               Right-Rotate(t)04          Else05               If s[left[right[t]]>s[right[t]] then   //case206                    Left-Rotate(left[t])07                     Right-Rotate(t)08          Else                                   //needn’t repair09               Exit10     Else11          If s[right[right[t]]>s[left[t]] then      //case1'12               Left-Rotate(t)13          Else14               If s[right[left[t]]>s[left[t]] then     //case2'15                    Right-Rotate(right[t])16                    Left-Rotate(t)17          Else                                    //needn’t repair18               Exit19     Maintain(left[t],false)                     //repair the left subtree20     Maintain(right[t],true)                     //repair the right subtree21     Maintain(t,false)                           //repair the whole tree22     Maintain(t,true)                            //repair the whole tree

为什么Maintain(left[t],true)和Maintain(right[t],false)被省略了呢？您可以在陈启峰论文第六部分的分析中找到答案。

其他可以从论文中获得的信息：每次SBT后树的总深度递减的证明；Maintain的平摊运行时间是O(1)的证明（也就是说你不必担心Maintain这个递归过程是否会永不停止）等。

[] 基本操作

[] 查找

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

Search(x,k)1     if x=NULL or k=key[x] //找到了目标节点或目标节点不存在则返回x2        then return x3     if k

[] 取大/取小

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

[] 后继

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

[] 前趋

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

[] 插入

SBT的插入操作很简单。它仅仅比普通BST的多出了一个Maintain操作和对s的简单维护。下面这个过程将一个节点v插入SBT中。

Insert (t,v)1     If t=0 then2        t ← v3     Else4        s[t] ← s[t]+15         If v

[] 删除

与普通维护size域的BST删除相同。

关于无需Maintain的说明by sqybi：

在删除之前，可以保证整棵树是一棵SBT。当删除之后，虽然不能保证这棵树还是SBT，但是这时整棵树的最大深度并没有改变，所以时间复杂度也不会增加。这时，Maintain就显得是多余的了。

[] 动态顺序统计操作

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

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

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

Select(x,i)1     r ← size[left[x]] + 12     if(i=r)3          then return x4     else if i
   
      using namespace std;  ifstream fin("cashier.in");  ofstream fout("cashier.out");  const unsigned int MAX_N=100001;  int ZUISHAO;     //最低工资  int ADD_PAY=0;  unsigned int C_NUM=0;  int front = 0;  struct node  {    int key;    int size, llink, rlink;  }OIER[MAX_N];  void LeftRotate(int &x)//左旋  {    int y = OIER[x].rlink;    if (y == 0) return;    OIER[x].rlink = OIER[y].llink;    OIER[y].llink = x;    OIER[y].size = OIER[x].size;    OIER[x].size = OIER[OIER[x].llink].size+OIER[OIER[x].rlink].size+1;    x = y;  }  void RightRotate(int &x)//右旋  {    int y = OIER[x].llink;    if (y == 0) return;    OIER[x].llink = OIER[y].rlink;    OIER[y].rlink = x;    OIER[y].size = OIER[x].size;    OIER[x].size = OIER[OIER[x].llink].size+OIER[OIER[x].rlink].size+1;    x = y;  }  void Maintain(int &root, bool flag)//维护 SBT 树  {    if (!root) return;    if (flag)    {        if(OIER[root].llink && OIER[OIER[root].llink].llink            && (!OIER[root].rlink || OIER[OIER[OIER[root].llink].llink].size > OIER[OIER[root].rlink].size))            RightRotate(root);        else if(OIER[root].llink && OIER[OIER[root].llink].rlink            && (!OIER[root].rlink || OIER[OIER[OIER[root].llink].rlink].size > OIER[OIER[root].rlink].size))        {            LeftRotate(OIER[root].llink);            RightRotate(root);        }        else return;    }    else    {        if (OIER[root].rlink && OIER[OIER[root].rlink].rlink            && (!OIER[root].llink || OIER[OIER[OIER[root].rlink].rlink].size > OIER[OIER[root].llink].size))            LeftRotate(root);        else if (OIER[root].rlink && OIER[OIER[root].rlink].llink            && (!OIER[root].llink || OIER[OIER[OIER[root].rlink].llink].size > OIER[OIER[root].llink].size))        {            RightRotate(OIER[root].rlink);            LeftRotate(root);        }        else return;    }    Maintain(OIER[root].llink, true);    Maintain(OIER[root].rlink, false);    Maintain(root, true);    Maintain(root, false);  }  void Insert(int &root, int x)//插入关键字 x  {    if (!root)    {        root = ++front;        OIER[root].key = x;        OIER[root].size = 1;    }    else    {        ++OIER[root].size;        Insert(x <= OIER[root].key ? OIER[root].llink : OIER[root].rlink, x);        Maintain(root, x <= OIER[root].key);    }  }  int Delete(int &root)//删除  {     int t=0,sum=0;     if(!root) return root;     if(OIER[root].key+ADD_PAY
    
     r) return Select(OIER[R].llink, x-r);    if(x==r) return OIER[R].key;    }   int main(void)  {    unsigned int N;    char command;    int pay,root=0;    int i;    fin>>N>>ZUISHAO;    for(i=1;i<=N;i++)       {          fin>>command>>pay;          if(command=='I'){                  if(pay>=ZUISHAO)Insert(root,pay-ADD_PAY);                                                                         }          if(command=='F'){                           if(pay>OIER[root].size) fout<<-1<

你可能感兴趣的文章