woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

从B树谈到R树之B树的c实现

http://blog.csdn.net/v_july_v/article/details/6735293(该博客值得深入翻阅)

 

 B树谈到R树之B树的c实现

作者:weedgeJuly。编程艺术室出品。

前言

    代码大全的作者Steve McConnell曾称,他所见识的任何一本书都不是某一个人能完全独立即能完成的。吾深以为然。

    blog内的文章十有八九系我个人参考资料原创所作,同时十有二三系本人与吾的朋友共同创作完成。所以,诸君在浏览本博客内任何一篇文章时,务必尊重他人劳动成果。当然,有任何问题,欢迎随时不吝指正。

    ok,在本blog之前的一篇文章中:B树、B+树、B*树谈到R ,各位读者反应热烈。这次,咱们来编码实现B树的查找,插入,删除等操作。同时此文也算作是上一篇文章从B树谈到R树的续。望诸君不吝赐教。谢谢。

第一部分、B树的查找,插入,删除等具体操作

    编码实现B树之前,咱们先来回顾一下上文中所给出的B树的查找,插入,删除等具体的操作都是怎么一回事儿。明白了原理之后,再来编程实现,就相对来说有方向感了。ok,请看下文(援引自B树、B+树、B*树谈到R 3小节):

B树的插入、删除操作

    上文第3小节简单介绍了利用B树这种结构如何访问外存磁盘中的数据的情况,下面咱们通过另外一个实例来对这棵B树的插入(insert,删除(delete)基本操作进行详细的介绍。

    但在此之前,咱们还得简单回顾下一棵m阶的B (m叉树)的特性,如下:

  1. 树中每个结点含有最多含有m个孩子,即m满足:ceil(m/2)<=m<=m
  2. 除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子(其中ceil(x)是一个取上限的函数);
  3. 若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);
  4. 所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点,实际上这些结点不存在,指向这些结点的指针都为null)
  5. 每个非终端结点中包含有n个关键字信息: (nP0K1P1K2P2......KnPn)。其中:
           a)   Ki (i=1...n)
    为关键字,且关键字按顺序升序排序K(i-1)< Ki
           b)   Pi
    为指向子树根的接点,且指针P(i-1)指向子树种所有结点的关键字均小于Ki,但都大于K(i-1) 
           c)  
    除根结点之外的结点的关键字的个数n必须满足: [ceil(m / 2)-1]<= n <= m-1(叶子结点也必须满足此条关于关键字数的性质,根结点除外)。

    ok,下面咱们以一棵5阶(m=5,即除根结点和叶子结点之外的内结点最多5个孩子,最少3个孩子)B树实例进行讲。

备注:

  • 关键字数(2-4个)针对--非根结点(包括叶子结点在内),孩子数(3-5个)--针对根结点和叶子结点之外的内结点。当然,根结点是必须至少有2个孩子的,不然就成直线型搜索树了。
  • 我说的再明白点就是,一棵5阶的B树中任何一个结点的关键字数是1-4,孩子树是2-5。同时,一棵5阶的B树的最大高度应为log_ceil(m/2)N(下划线表示以ceil(m/2)为底)。

下图中关键字为大写字母,顺序为字母升序。

结点定义如下:

typedef struct{
   int Count;         //
当前节点中关键元素数目
   ItemType Key[4];   //
存储关键字元素的数组
   long Branch[5];    //
伪指针数组,(记录数目)方便判断合并和分裂的情况
} NodeType;

 

clip_image001

1.1、插入(insert)操作

    插入一个元素时,首先在B树中是否存在,如果不存在,即在叶子结点处结束,然后在叶子结点中插入该新的元素,注意:

  • 如果叶子结点空间足够,这里需要向右移动该叶子结点中大于新插入关键字的元素,
  • 如果空间满了以致没有足够的空间去添加新的元素,则将该结点进行分裂,将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中(当然,如果父结点空间满了,也同样需要分裂操作),而且当结点中关键元素向右移动了,相关的指针也需要向右移。
  • 如果在根结点插入新元素,空间满了,则进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层。

1、咱们通过一个实例来逐步讲解下。插入以下字符字母到一棵空的B 树中(非根结点关键字数小了(小于2个)就合并,大了(超过4个)就分裂):C N G A H E K Q M F W L T Z D P R X Y S,首先,结点空间足够,4个字母插入相同的结点中,如下图:

 clip_image002

2、当咱们试着插入H时,结点发现空间不够,以致将其分裂成2个结点,移动中间元素G上移到新的根结点中,在实现过程中,咱们把AC留在当前结点中,而HN放置新的其右邻居结点中。如下图:

 clip_image003

3、当咱们插入E,K,Q时,不需要任何分裂操作

clip_image004

4、插入M需要一次分裂,注意M恰好是中间关键字元素,以致向上移到父节点中

 

clip_image005

5、插入F,W,L,T不需要任何分裂操作

 

clip_image006

6、插入Z时,最右的叶子结点空间满了,需要进行分裂操作,中间元素T上移到父节点中,注意通过上移中间元素,树最终还是保持平衡,分裂结果的结点存在2个关键字元素。

 

clip_image007

7、插入D时,导致最左边的叶子结点被分裂,D恰好也是中间元素,上移到父节点中,然后字母P,R,X,Y陆续插入不需要任何分裂操作(别忘了,树中至多5个孩子)。

 

clip_image008

8、最后,当插入S时,含有N,P,Q,R的结点需要分裂,把中间元素Q上移到父节点中,但是情况来了,父节点中空间已经满了,所以也要进行分裂,将父节点中的中间元素M上移到新形成的根结点中,注意以前在父节点中的第三个指针在修改后包括DG节点中。这样具体插入操作的完成,下面介绍删除操作,删除操作相对于插入操作要考虑的情况多点。

 

clip_image009

1.2、删除(delete)操作

    首先查找B树中需删除的元素,如果该元素在B树中存在,则将该元素在其结点中进行删除,如果删除该元素后,首先判断该元素是否有左右孩子结点,如果有,则上移孩子结点中的某相近元素到父节点中,然后是移动之后的情况;如果没有,直接删除后,移动之后的情况。

    删除元素,移动相应元素之后,

  • 如果某结点中元素数目(即关键字数)小于ceil(m/2)-1,则需要看其某相邻兄弟结点是否丰满(结点中元素个数大于ceil(m/2)-1)(还记得第一节中关于B树的第5个特性中的c点么? c)除根结点之外的结点(包括叶子结点)的关键字的个数n必须满足: ceil(m / 2)-1<= n <= m-1m表示最多含有m个孩子,n表示关键字数。在本小节中举的一颗B树的示例中,关键字数n满足:2<=n<=4),
  • 如果丰满,则向父节点借一个元素来满足条件;
  • 如果其相邻兄弟都刚脱贫,即借了之后其结点数目小于ceil(m/2)-1,则该结点与其相邻的某一兄弟结点进行合并成一个结点,以此来满足条件。

    那咱们通过下面实例来详细了解吧。

    以上述插入操作构造的一棵5B树(树中最多含有mm=5)个孩子,因此关键字数最小为ceil(m / 2)-1=2还是这句话,关键字数小了(小于2个)就合并,大了(超过4个)就分裂)为例,依次删除H,T,R,E

clip_image009

1、首先删除元素H,当然首先查找HH在一个叶子结点中,且该叶子结点元素数目3大于最小元素数目ceil(m/2)-1=2,则操作很简单,咱们只需要移动K至原来H的位置,移动LK的位置(也就是结点中删除元素后面的元素向前移动)

 

clip_image010

2、下一步,删除T,因为T没有在叶子结点中,而是在中间结点中找到,咱们发现他的继承者W(字母升序的下个元素),将W上移到T的位置,然后将原包含W的孩子结点中的W进行删除,这里恰好删除W后,该孩子结点中元素个数大于2,无需进行合并操作。

 

clip_image011

3、下一步删除RR在叶子结点中,但是该结点中元素数目为2,删除导致只有1个元素,已经小于最小元素数目ceil(5/2)-1=2,而由前面我们已经知道:如果其某个相邻兄弟结点中比较丰满(元素个数大于ceil(5/2)-1=2),则可以向父结点借一个元素,然后将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中(有没有看到红黑树中左旋操作的影子?),在这个实例中,右相邻兄弟结点中比较丰满(3个元素大于2),所以先向父节点借一个元素W下移到该叶子结点中,代替原来S的位置,S前移;然后X在相邻右兄弟结点中上移到父结点中,最后在相邻右兄弟结点中删除X,后面元素前移。

 

clip_image012

4、最后一步删除E 删除后会导致很多问题,因为E所在的结点数目刚好达标,刚好满足最小元素个数(ceil(5/2)-1=2,而相邻的兄弟结点也是同样的情况,删除一个元素都不能满足条件,所以需要该节点与某相邻兄弟结点进行合并操作;首先移动父结点中的元素(该元素在两个需要合并的两个结点元素之间)下移到其子结点中,然后将这两个结点进行合并成一个结点。所以在该实例中,咱们首先将父节点中的元素D下移到已经删除E而只有F的结点中,然后将含有DF的结点和含有A,C的相邻兄弟结点进行合并成一个结点。

 

clip_image013

5、也许你认为这样删除操作已经结束了,其实不然,在看看上图,对于这种特殊情况,你立即会发现父节点只包含一个元素G,没达标(因为非根节点包括叶子结点的关键字数n必须满足于2=<n<=4,而此处的n=1),这是不能够接受的。如果这个问题结点的相邻兄弟比较丰满,则可以向父结点借一个元素。假设这时右兄弟结点(含有Q,X)有一个以上的元素(Q右边还有元素),然后咱们将M下移到元素很少的子结点中,将Q上移到M的位置,这时,Q的左子树将变成M的右子树,也就是含有NP结点被依附在M的右指针上。所以在这个实例中,咱们没有办法去借一个元素,只能与兄弟结点进行合并成一个结点,而根结点中的唯一元素M下移到子结点,这样,树的高度减少一层。

 

clip_image014

为了进一步详细讨论删除的情况,再举另外一个实例

这里是一棵不同的5B树,那咱们试着删除C

 

clip_image015

于是将删除元素C的右子结点中的D元素上移到C的位置,但是出现上移元素后,只有一个元素的结点的情况。

又因为含有E的结点,其相邻兄弟结点才刚脱贫(最少元素个数为2),不可能向父节点借元素,所以只能进行合并操作,于是这里将含有A,B的左兄弟结点和含有E的结点进行合并成一个结点。

 

clip_image016

这样又出现只含有一个元素F结点的情况,这时,其相邻的兄弟结点是丰满的(元素个数为3>最小元素个数2),这样就可以想父结点借元素了,把父结点中的J下移到该结点中,相应的如果结点中J后有元素则前移,然后相邻兄弟结点中的第一个元素(或者最后一个元素)上移到父节点中,后面的元素(或者前面的元素)前移(或者后移);注意含有KL的结点以前依附在M的左边,现在变为依附在J的右边。这样每个结点都满足B树结构性质。

 

clip_image017

从以上操作可看出:除根结点之外的结点(包括叶子结点)的关键字的个数n满足:(ceil(m / 2)-1<= n <= m-1,即2<=n<=4。这也佐证了咱们之前的观点。删除操作完。

第二部分、B树的编码实现

    既然明白了B树的插入,和删除操作的原理,接下来,咱们来一步一步实现它。不过,有一点必须说明的是:这个实现只是实现了偶数序order(阶)的情况;还有奇数序order(阶)的情况没有考虑。待日后改进。

  • ok,以下是头文件:

  • 下面是B树的实现文件:

  • 最后,给出测试文件:

参考

  • http://www.cppblog.com/converse/archive/2009/10/13/98521.html

联系作者:

    若有任何问题,欢迎随时不吝指正。或者联系我们:

后记:

    blog日后会更多的关注数据结构与算法之外的东西,如分布式架构,海量数据处理,搜索引擎相关。毕竟,算法之外的东西,如瀚海般无止境,要学的东西,还有很多。

    若转载,请注明出处,谢谢。完。二零一一年八月三十一日。

 

posted on 2011-09-01 11:02 肥仔 阅读(2202) 评论(0)  编辑 收藏 引用 所属分类: C++ 基础数据库


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理