B树——思路、及C语言代码的达成
发布时间：2021-11-19 12:57:55 所属栏目：教程 来源：互联网
导读：本人现读本科大二，这学期学习数据结构，老师为我们的期末作业布置一道任选题，而我一直以来都有听说B树是一棵挺神奇的树，所以我选择了它，当然更重要的原因是因为B树的难度最高，我喜欢做有挑战性的工作。同时，我听我基友说他热衷于将自己所学所想分享到
|
本人现读本科大二，这学期学习数据结构，老师为我们的期末作业布置一道任选题，而我一直以来都有听说B树是一棵挺神奇的树，所以我选择了它，当然更重要的原因是因为B树的难度最高，我喜欢做有挑战性的工作。同时，我听我基友说他热衷于将自己所学所想分享到博客园上，故才有了这样一篇文章。希望我能够在写博客的同时学习到更多东西，同时也能帮助到其他遇到或者即将遇到雷同问题的初学者们。 1.关于B树 B树是一种称之为查找树的树，与之类似的有查找二叉树，平衡二叉树，除此之外，还有各种B树的兄弟姐妹B+树、B-树、B*树等，他们共同的特点就是都是按照一定的顺序规律存储的。B树的应用也是很广泛的，B树是几乎所有数据库的默认索引结构，也是用的最多的索引结构。B树是一种多叉树，根据其最多叉的数目可以直接称为M阶B树。根据算法导论上叙述，还可按B树每个节点最少的分支确定一棵B树的阶，但是这样的话B树的阶便必须为偶数。我个人是使用根据最大分支的数目确定B树的阶的。 下图就是某一棵B树，每一个结点中都包含有数个数据元素，而同时一定会有数据元素的个数加一个的子树。 一棵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阶树上限要求，再进行递归的分裂操作。 /*** * @name Status insertBTree(BTree &T, Record e) * @description 插入实现元素的插入 * @return 成功返回OK,如果存在则返回FALSE，否则返回ERROR * @notice ***/ Status insertBTree(BTree &T, Record e) { BTree p; int index, temp; Status find_flag; if (NULL == T)//考虑B树为空树的情况 { T = (BTree)malloc(BTLEN); if (NULL == T) return OVERFLOW; T->keynum = 1; T->parent = NULL; for (index = 0;index <= m; ++index) { T->ptr[index] = NULL; T->key[index] = 0; } T->key[1] = e.key; return OK; } find_flag = findBTree(T, p, temp, e.key);//寻找插入节点 if (find_flag == TRUE) { return FALSE; } if (find_flag == FALSE) { //不管怎样先直接插入 p->keynum++; for (index = p->keynum;index > temp;--index) { p->key[index] = p->key[index - 1]; p->ptr[index] = p->ptr[index - 1]; } p->ptr[temp] = NULL; p->key[temp] = e.key; if (p->keynum == m) //这种情况得分裂 { splitBTree(p); } renewParent(T); return OK; } return ERROR; }  （编辑：PHP编程网 - 黄冈站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330482号