B树——思路、及C语言代码的实现

宜家博客
宜家博客
宜家博客
48010
文章
0
评论
2020年7月1日15:02:46 评论 1 1004字阅读3分20秒

0.序

  本人现读本科大二,这学期学习数据结构,老师为我们的期末作业布置一道任选题,而我一直以来都有听说B树是一棵挺神奇的树,所以我选择了它,当然更重要的原因是因为B树的难度最高,我喜欢做有挑战性的工作。同时,我听我基友说他热衷于将自己所学所想分享到博客园上,故才有了这样一篇文章。希望我能够在写博客的同时学习到更多东西,同时也能帮助到其他遇到或者即将遇到雷同问题的初学者们。

1.关于B树

  B树是一种称之为查找树的树,与之类似的有查找二叉树,平衡二叉树,除此之外,还有各种B树的兄弟姐妹B+树、B-树、B*树等,他们共同的特点就是都是按照一定的顺序规律存储的。B树的应用也是很广泛的,B树是几乎所有数据库的默认索引结构,也是用的最多的索引结构。B树是一种多叉树,根据其最多叉的数目可以直接称为M阶B树。根据算法导论上叙述,还可按B树每个节点最少的分支确定一棵B树的阶,但是这样的话B树的阶便必须为偶数。我个人是使用根据最大分支的数目确定B树的阶的。

  下图就是某一棵B树,每一个结点中都包含有数个数据元素,而同时一定会有数据元素的个数加一个的子树。

B树——思路、及C语言代码的实现

  一棵M阶B树或为空树,或为满足下列特性的M叉树:

(1)树中每个结点最多含有M棵子树;

(2)若根结点不是叶子结点,则至少有2棵子树;

(3)除根结点之外的所有非终端结点至少有[m/2]棵子树;

(4)每个非终端结点中包含的信息keynum,ptr[0],key[1],ptr[1],key[2],ptr[2],……key[keynum],ptr[keynum];

  其中,key为关键字,且关键字按升序排序,ptr为指向子树的根结点指针

2.思路及实现

  B树的接口主要是插入(包括空树插入一个元素)和删除操作,而插入和删除操作不可避免的都会用到查找操作,而查找的主要思路比较简单,主要是利用B树是一种排序树的原理,可以很快找到要插入位置或者要删除结点。这里的关键是注意返回内容包括查找结果所在结点,以及该元素所在位置,这是为了方便接下来的操作比较简单。

插入:

  通过对B树进行遍历,找出要插入的结点以及结点位置,如果找到的key值在B树当中已经存在,则说明插入失败,否则,就可以进行插入操作。这里可以先不管是否超出M阶树的上限要求,因为我们在定义的时候会故意留下一个位置,可以存放多余的一个元素,插入之后,通过判断是否达到M阶树上限要求,再进行递归的分裂操作。

继续阅读
weinxin
欢迎加入中国站长博客之家
本站的所有资源都会上传分享到博客之家,希望大家互相学习交流进步。
宜家博客
Python 面向对象编程 Linux编程

Python 面向对象编程

  Python从设计之初就已经是一门面向对象的语言,正因为如此,在Python中创建一个类和对象是很容易的。本章节我们将详细介绍Python的面向对象编程。   如果你以前没有接触过面向对象的编程语...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: