数据结构之B树
1.0 简介
1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,
它是一种平衡的多叉树,称为B树(或B-树、B_树)。
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树:
1、根结点至少有两个子女;
2、每个节点最多有m颗子树
3、若根结点不是终端结点,则至少有两颗子树
4、除了根结点之外的非终端节点至少有 个子树
所有的非终端节点都包含以下数据(n,P0,K1,P1,K2,P2,…,Kn,Pn)
n为关键码的个数
p 为指向孩子节点的指针 并且 遵循 假设 K1 < ,P1, < K2,
k为 关键码.
如图:
B树是2-3树的推广 2-3树是一个三阶B树
B树 通常用在文件系统中
2.0 B树的操作
主要是查找 删除 插入
2.1 查找
这个类似2-3树的 查找 例如我们在上述的图中查找53 首先根结点 查找,和35比 大于35 去右子树查找,然后和大于43小于78 进入43 与78中间的子树查找,然后在子节点顺序比较关键码,最终找到53,如果没有 则查找失败
2.2 插入
- 能插就插
- 插不进去硬插
2.3 删除
- 如果要删除的结点的关键码的个数大于 m/2 则直接删除
- 如果关键码的个数不大于 m/2 后,那么如果兄弟有 那么就向兄弟借,这个过程 要改变双亲结点
- 如果兄弟节点不够呢?那么就合并,就是把要出这个节点合并到他的兄弟节点中,然后删除这个空节点,这时候双亲结点少了一个子节点,怎么办呢?双亲结点关键码下移到我们合并后的结点中,如果双亲结点没有下溢,就是说没有少于m/2个,那么算法结束
- 否则 双亲结点也要进行上述操作