现在的位置: 首页 > 综合 > 正文

SBT树!

2012年08月29日 ⁄ 综合 ⁄ 共 5931字 ⁄ 字号 评论关闭

在今年的信息学冬令营上,陈启峰提出了一个自己创造的BST数据结构—Size
Balanced Tree
。这个平衡二叉树被全世界内的许多网站所讨论,大家讨论的主题也只有一个—SBT能够取代Treap吗?本文详细介绍SBT树的性质,以及一些常用的操作,最后证明SBT是一颗高度平衡的二分查找树。

一.       
介绍

众所周知,BST能够快速的实现查找等动态操作。但是在某些情况下,比如将一个有序的序列依次插入到BST中,则BST会退化成为一条链,效率非常之低。由此引申出来很多平衡BST,比如AVL树,红黑树,treap树等。这些数据结构都是通过引入其他一些性质来保证BST的高度在最坏的情况下都保持在O(log
n)
。其中,AVL树和红黑树的很多操作都非常麻烦,因此实际应用不是很多。而treap树加入了一些随机化堆的性质,实际应用效果非常好,实现起来很简单,一直以来受到很多人的青睐。本文介绍一种新的平衡BST树,实现起来也是非常之简单,并且能够支持更多的操作,实际评测效率跟treap也不差上下。

在介绍SBT之前,先介绍一下BST以及在BST上的旋转操作。

1.     
Binary Search Tree

BST是一种高级的数据结构,它支持很多动态操作,包括查找,求最小值,最大值,前驱,后继,插入和删除,能够用于字典以及优先队列。

       BST是一棵二叉树,每个结点最多有2个儿子。每个结点都有个键值,并且键值必须满足下面的条件:

       如果xBST中的一个结点。那么x的键值不小于其左儿子的键值,并且不大于其右儿子的键值。

       对于每个结点t,用left[t]right[t]分别来存放它的两个儿子,ket[t]存放该结点的键值。另外,在SBT中,要增加s[t],用来保存以t为根的子树中结点的个数。

2.     
旋转

为了保证BST的平衡(不会退化成为一条链),通常通过旋转操作来改变BST的结构。旋转操作不会影响binary-search-tree的性质!


       2.1右旋操作的伪代码

       右旋操作必须保证左儿子存在

       Right-Rotate(t)

              k←left[t]

              left[t]←right[k]

              right[k]←t

              s[k]←s[t]

              s[t]←s[left[t]]+s[right[t]]+1

              t←k

       2.2 左旋操作的伪代码

       左旋操作必须保证右儿子存在

       Left-Rotate(t)

              k←right[t]

              right[t]←left[k]

              left[k]←t

              s[k]←s[t]

              s[t]←s[left[t]]+s[right[t]]+1

              t←k

        

二.Size Balanced Tree

Size Balanced Tree(简称SBT)是一种平衡二叉搜索树,它通过子树的大小s[t]来维持平衡性质。它支持很多动态操作,并且都能够在O(log n)的时间内完成。

Insert(t,v)

将键值为v的结点插入到根为t的树中

Delete(t,v)

在根为t的树中删除键值为v的结点

Find(t,v)

在根为t的树中查找键值为v的结点

Rank(t,v)

返回根为t的树中键值v的排名。也就是树中键值比v小的结点数+1

Select(t,k)

返回根为t的树中排名为k的结点。同时该操作能够实现Get-min,Get-max,因为Get-min等于Select(t,1),Get-max等于Select(t,s[t])

Pred(t,v)

返回根为t的树中比v小的最大的键值

Succ(t,v)

返回根为t的树中比v大的最小的键值

SBT树中的每个结点都有leftrightkey以及前面提到的size域。SBT能够保持平衡性质是因为其必须满足下面两个条件:

对于SBT中的每个结点t,有性质(a)(b)

(a). s[right[t]]≥s[left[left[t]]],s[right[left[t]]]

(b). s[left[t]]≥s[right[right[t]]],s[left[right[t]]]


即在上图中,有s[A],s[B]≤s[R]&s[C],s[D] ≤s[L]

三.            
 Maintain

假设我们要在BST中插入一个键值为v的结点,一般是用下面这个过程:

Simple-Insert(t,v)

        If
t=0 then

            t←NEW-NODE(v)

              Else

                     s[t]←s[t]+1

                     If
v<key[t] then

                            Simple-Insert(left[t],v)

                     Else

                            Simple-Insert(right[t],v)

执行完操作Simple-Insert后,SBT的性质(a)(b)就有可能不满足了,这是我们就需要修复(Maintain)SBT

Maintain(t)用来修复根为tSBT,使其满足SBT性质。由于性质(a)(b)是对称的,下面仅讨论对性质(a)的修复。

Case 1s[left[left[t]]]>s[right[t]]


这种情况下可以执行下面的操作来修复SBT

执行Right-Rotate(T)

有可能旋转后的树仍然不是SBT,需要再次执行Maintain(T)

由于L的右儿子发生了变化,因此需要执行Maintain(L)

Case 2s[right[left[t]]]>s[right[t]]

这种情况如下图所示:


需要执行一下步骤来修复SBT

执行Left-Rotate(L)。如下图所示


执行Right-Rotate(T)。如下图所示


当执行完(1)(2)后,树的结构变得不可预测了。但是幸运的是,在上图中,A,E,F,R子树仍然是SBT。因此我们可以执行Maintain(L)Maintain(T)来修复B的子树。

Case 3

这种情况和case 1是对称的

Case 4

这种情况和case 2是对称的

Maintain操作的伪代码:

Maintain过程中,用一个变量flag来避免额外的检查。当flagfalse时,代表case 1case 2需要被检查,否则case 3case 4需要被检查。

Maintain
(t,flag)

If flag=false
then

             If s[left[left[t]]>s[right[t]]
then

                    Right-Rotate(t)

             Elseif s[right[left[t]]>s[right[t]]
then

                    Left-Rotate(left[t])

                    Right-Rotate(t)

             Else exit

      Elseif s[right[right[t]]>s[left[t]]
then

             Left-Rotate(t)

      Elseif s[left[right[t]]>s[left[t]]
then

             Right-Rotate(right[t])

             Left-Rotate(t)

      Else exit

      Maintain(left[t],false)

Maintain(right[t],true)

Maintain(t,false)

      Maintain(t,true)

四.常用操作

插入操作

SBT和插入操作和BST的基本相同,只是在插入之后需要执行下Maintain操作。

Insert
(t,v)

If t=0 then

t←NEW-NODE(v)

Else

s[t]
←s[t]+1

If v<key[t]
then

Simple-Insert(left[t],v)

Else

Simple-Insert(right[t],v)

Maintain(t,v≥key[t])

删除操作

如果没有找到要删除的结点,那么就删除最后一个访问的结点并记录。

Delete
(t,v)

If s[t]2 then

record←key[t]

t←left[t]+right[t]

Exit

s[t] ←s[t]1

If v=key[t] then

Delete(left[t],v[t]+1)

Key[t] ←record

Maintain(t,true)

Else

If v<key[t] then

Delete(left[t],v)

Else

Delete(right[t],v)

Maintain(t,v<key[t])

另外,由于SBT的平衡性质是靠size域来维护的,而size域本身(子树所含节点个数)对于很多查询算法都特别有用,这样使得查询集合里面的譬如第n小的元素,以及一个元素在集合中的排名等操作都异常简单,并且时间复杂度都稳定在O(log n)。下面仅介绍下上表提到的select(t,k)操作和rank(t,v)操作。

       由于SBT的性质(结点t的关键字比其左子树中所有结点的关键字都大,比其左子树中所有的关键字都小),理解下面的算法非常容易。

3Select操作

Select(t,k)

       If k=s[left[t]]+1 then

              return
key[t]

       If k<=s[left[t]] then

              return
Select(left[t],k)

       Else

              return
Select(right[t],k-1-s[left[t]])

4Rank操作

Rank(t,v)

       If t=0 then

              return
1

       If v<=key[t] then

              return
rank(left[t],v)

       Else

              return
s[left[t]]+1+rank(right[t],v)

同样,求前驱结点的操作Pred和后继结点的操作都很容易通过size域来实现。

 

五.相关证明分析

显然Maintain操作是一个递归过程,可能你会怀疑它是否会结束。下面我们可以证明Maintain操作的平摊时间复杂度为O(1)

1.关于树的高度的分析

f[h]表示高度为hSBT中结点数目的最小值,则有

                             1                                    (h=0)

f[h]=       2                              
     (h=1)

           f[h-1]+f[h-2]+1                  (h>1)

a.证明:

(1)      
很明显f[0]=1,f[1]=2

(2)      
首先,对于任意h>1,我们假设t是一颗高度为hSBT的根结点,则这颗SBT包含一颗高度为h-1的子树。不妨假设t的左子树的高度为h-1,根据f[h]的定义,有

s[left[t] ]≥f[h-1],同样的,左子树中有一颗高度为h-2的子树,换句话说,左子树中含有一颗结点数至少为f[h-2]的子树。由SBT的性质(b),可知s[right[t]]
≥f[h-2]。因此我们有s[t]=s[left[t]]+s[right[t]]+1≥f[h-1]+f[h-2]+1。

另外一方面,我们可以构造一颗高度为h,并且结点数正好为f[h]SBT,称这样的SBTtree[t]。可以这样来构造tree[h]

                             含有一个结点的SBT                                    (h=0)

tree[h]=     含有2个结点的任意SBT                     
       (h=1)

         左子树为tree[h-1],右子树为tree[h-2]SBT    (h>1)

f[h]的定义可知f[h] f[h-1]+f[h-2]+1(h>1)。因此f[h]的上下界都为f[h-1]+f[h-2]+1,因此有f[h]=f[h-1]+f[h-2]+1

b.最坏情况下的高度

事实上f[h]是一个指数函数,通过f[h]的递推可以计算出通项公式。


定理:

含有n个结点的SBT在最坏情况下的高度是满足f[h] n的最大的h值。

假设maxh为含有n个结点的SBT的最坏情况下的高度。由上面的定理,有

                                  

于是很明显SBT的高度为O(logn),是一颗高度平衡的BST

2.对Maintain操作的分析

通过前面的计算分析我们能够很容易分析出Maintain操作是非常高效的。

首先,有一个非常重要的值来评价一颗BST的好坏:所有结点的平均深度。它是通过所有结点的深度之和SD除以结点个数n计算出来的。一般来说,这个值越小,这颗BST就越好。由于对于一颗BST来说,结点数n是一个常数,因此我们期望SD值越小越好。

现在我们集中来看SBTSD值,它的重要性在于能够制约Maintain操作的执行时间。回顾先前提到的BST中的旋转操作,有个重要的性质就是:每次执行旋转操作后,SD值总是递减的!

由于SBT树的高度总是O(log n),因此SD值也总是保持在Olog n)。并且SD仅在插入一个结点到SBT后才增加,因此(TMaintain操作中执行旋转的次数)

Maintain操作的次数等于T加上不需要旋转操作的Maintain操作的次数。由于后者为O(nlogn)+O(T),因此Maintain的平摊分析时间复杂度为:


对各个操作时间复杂度的分析

现在我们知道了SBT的高度为O(log n),并且 Maintain操作的平摊分析时间复杂度为O(1),因此对于所有的常用操作,时间复杂度都稳定在O(log n)

抱歉!评论已关闭.