07-7.4.1 B树

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

五叉查找树

struct Node{
	ElemType keys[4];  // 最多四个关键字
	struct Node * child[5];  // 最多五个孩子
	int num;  // 结点中有几个关键字
};

如何保证查找效率

若每个节点内关键字太少，导致树变高，要查找更多层结点，效率低

策略：m 叉查找树中，规定除了根结点外，任何结点至少有$[m/2]$个分叉，即至少有$[m/2]-1$个关键字
举例：对于5叉排序树，规定除了根结点外，任何结点都至少有3个分叉，2个关键字

B树

又称多路平衡查找树，B树中所被允许的孩子个数的最大值称为B树的阶，通常用m表示。一颗m阶B树或为空树，或为满足如下特性的m叉树：

1. 树中每个节点至多有m棵子树，即至多含有m-1个关键字
2. 若根结点不是终端结点，则至少有两棵子树
3. 除根结点外的所有非叶结点至少有$[m/2]$棵子树，即至少含有$[m/2]-1$个关键字
4. 所有的叶子结点都出现在同一层次上，并且不带信息

高度（不包括叶子结点）

问：含n个关键字的m阶B树，最小高度、最大高度是多少？
最小高度 —— 让每个结点尽可能满，有m-1个关键字，m个分叉，则有
$$h\ge lo{g}_m(n+1)$$
最大高度 —— 让各层的分叉尽可能少，即根结点只有两个分叉，其他节点只有$(m/2)$ 个分叉，各层结点至少有：第一层1，第二层2，第三层$2(m/2)$…第h层$2(m/2{)}^{h-2}$
第h+1层共有叶子结点（失败结点）$2(m/2{)}^{h-1}$ 个
n个关键字的B树必有n+1个叶子结点，则$n+1\le 2(m/2{)}^{h-1}$ ，即
$$h\le lo{g}_{(m/2)}\frac{n+1}{2}+1$$

插入

![[Pasted image 20240709115937.png]]
因为每个结点只能插入四个元素，再往里面插入位置就不够用了，这个时候需要分裂成一棵新的树
需要注意的是：新元素一定是插入到最底层“终端结点”，用“查找”来确定插入位置

核心要求：

1. 对于 m 阶 B树，除根结点外，结点关键字个数 $(m/2)-1\le n\le m-1$
2. 子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < ……

删除

若被删除关键字在终端结点，则直接删除该关键字（要注意节点关键字个数是否低于下限 $(m/2)-1$ ）

若被删除关键字在非终端结点，则用直接前驱或直接后继来替代被删除的关键字
直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
直接后继：当前关键字右侧指针所指子树中“最左下”的元素
对于非终端结点关键字的删除，必然可以转化为对终端结点的删除操作

若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该点 右/左 兄弟结点及其双亲结点（父子换位法）
说白了，当右兄弟很宽裕时，用当前结点的后继、后继的后继，来填补空缺

本质：要永远保证B树的特性

如果兄弟不够借，将关键字删除后与左/右兄弟结点及双亲结点中的关键字进行合并