我要评论
1 什么是b树
1.1 b树的背景
b树（b-tree）结构是一种高效存储和查询数据的方法，它的历史可以追溯到1970年代早期。b树的发明人rudolf bayer和edward m. mccreight分别发表了一篇论文介绍了b树。这篇论文是1972年发表于《acm transactions on database systems》中的，题目为"organization and maintenance of large ordered indexes"。
这篇论文提出了一种能够高效地维护大型有序索引的方法，这种方法的主要思想是将每个节点扩展成多个子节点，以减少查找所需的次数。b树结构非常适合应用于磁盘等大型存储器的高效操作，被广泛应用于关系数据库和文件系统中。
b树结构有很多变种和升级版，例如b+树，b*树和sb树等。这些变种和升级版本都基于b树的核心思想，通过调整b树的参数和结构，提高了b树在不同场景下的性能表现。
总的来说，b树结构是一个非常重要的数据结构，为高效存储和查询大量数据提供了可靠的方法。它的历史可以追溯到上个世纪70年代，而且在今天仍然被广泛应用于各种场景。
1.2 b 的含义
b-树的名称是由其发明者rudolf bayer提出的。bayer和mccreight从未解释b代表什么，人们提出了许多可能的解释，比如boeing、balanced、between、broad、bushy和bayer等。但mccreight表示，越是思考b-trees中的b代表什么，就越能更好地理解b-trees
1.3 b-树的度和阶
- 度（degree）：指树中节点孩子数
- 阶（order）：指所有节点孩子数最大值
如上图：度：节点4、2都是有两个孩子，所以度数为2；节点1、3、5、7、9 10都是没有孩子，所以度数为0；节点6 8有3个孩子，所以度数为3。而阶是指上图中树的所有节点中孩子最多的那个值，就是节点6 8有3个孩子，所以上图中树的阶数为3。
1.4 b-树的特性
一颗m叉的btree特性如下 ：
- 树中每个节点最多包含 m 个孩子，其中 m 称为b-树的阶。
- 除根节点与叶子节点外，其它每个节点至少有 ceil(m/2) 个孩子。
- 若根节点不是叶子节点，则至少有两个孩子。
- 所有的叶子节点都在同一层。
- 每个非叶子节点由 n 个关键字 key 与 n+1 个指针组成，其中 ceil(m/2)-1 <= n <= m-1 。
- 关键字按非降序排列，即节点中的第 i 个关键字大于等于第 i-1 个关键字。
- 指针 p[ i ] 指向关键字值位于第 i 个关键字和第 i+1 哥关键字之间的子树。
一棵 b-树具有以下性质：
特性1️⃣：每个节点 x 具有
1️⃣➖1️⃣ 属性 n，表示节点 x 中 key 的个数
1️⃣➖2️⃣ 属性 leaf，表示节点是否是叶子节点
1️⃣➖3️⃣ 节点 key 可以有多个，以升序存储
特性2️⃣：每个非叶子节点中的孩子数是 n + 1、叶子节点没有孩子
特性3️⃣：最小度数t（节点的孩子数称为度）和节点中键数量的关系如下：
| column 1 | column 2 |
|---|---|
| 最小度数t | 键数量范围 |
| 2 | 1 ~ 3 |
| 3 | 2 ~ 5 |
| 4 | 3 ~ 7 |
| … | … |
| n | (n-1) ~ (2n-1) |
其中，当节点中键数量达到其最大值时，即 3、5、7 … 2n-1，需要分裂
特性4️⃣：叶子节点的深度都相同
b-树与 2-3 树、2-3-4 树的关系
它们之间的关系：
- 2-3树是最小度数为2的b树，其中每个节点可以包含2个或3个子节点。
- 2-3-4树是最小度数为2的b树的一种特殊情况，其中每个节点可以包含2个、3个或4个子节点。
- b树是一种更加一般化的平衡树，可以适应不同的应用场景，其节点可以包含任意数量的键值，节点的度数取决于最小度数t的设定。
1.5 b-树演变过程示例
以5叉btree为例（度为5）为例，演示b树的演变过程
key的数量：可以根据公式推导ceil(m/2)-1<=n<=m-1。因为m为5，所以得2<=n<=4，即当n>4时，中间节点分裂到父节点，两边节点分裂。
演变过程如下：
进入网页后，选择max. degree = 5选项。本例模拟的是度数为5的情况下插入cngahekqmfwltzdprxys数据，后续网址和下半部分的配置不会再进行截取（均不会更改）
1️⃣ 依次插入前4个字母cnga后，b树演变为下图，此时b树为 4 个关键字 key（acgn） 与 n+1 = 5 个指针组成
2️⃣ 插入h，此时 n>4，中间元素g字母向上分裂到新的节点，分裂动图如下所示（后续分裂均是同理，过程可以到网站内自己感受，后续不再放置动图）
此时b树各个key和指针的关系如下图所示（每一个节点指针比key的数量多1，后续不再展示带指针图）
3️⃣ 插入e、k、q不需要分裂
4️⃣ 插入m，中间元素m字母向上分裂到父节点g
5️⃣ 插入f、w、l、t不需要分裂
6️⃣ 插入z，中间元素t向上分裂到父节点中
7️⃣ 插入d，中间元素d向上分裂到父节点中，然后插入p、r、x、y不需要分裂
8️⃣ 最后插入s，npqr节点n>5，中间节点q向上分裂，但分裂后父节点dgmt的n>5，中间节点m向上分裂
最终如下b树演化结果如下：
2 b-树的java实现
1️⃣➖1️⃣ 内部节点类node中含有属性：
- 关键字
- 孩子们
- 有效关键字个数
- 是否是叶子节点
- 最小度数 (最小孩子数)
1️⃣➖2️⃣ 内部节点类node中含有方法：
- 多路查找get(int key)
- 向指定索引处插入key，insertkey(int key, int index)
- 向指定索引处插入child，insertchild(node child, int index)
1️⃣➖3️⃣ 内部节点类node中含有内部工具方法：
- 移除指定index处的关键字removekey(int index)
- 移除最左边的关键字removeleftmostkey()
- 移除最右边的关键字removerightmostkey()
- 移除指定index处的孩子removechild(int index)
- 移除最左边的孩子removeleftmostchild()
- 移除最右边的孩子removerightmostchild()
- 获取index孩子处左边的兄弟childleftsibling(int index)
- 获取index孩子处右边的兄弟childrightsibling(int index)
- 复制当前节点的所有key和child到目标节点movetotarget(node target)
2️⃣➖1️⃣ b数类btree中含有属性：
- 根节点（node）
- 树中节点最小度数
- 最小key数目
- 最大key数目
2️⃣➖2️⃣ b数类btree中含有方法：
- 是否存在某索引contains(int key)
- 新增put(int key)
- 分裂split(node left, node parent, int index)
- 删除remove(int key)
- 平衡balance(node parent, node x, int i)
2.1 b树节点类node
实际 keys 应当改为 entries 以便同时保存 key 和 value，本文主要是为了学习b树的思想，所以做简化实现
static class node {
/**
* 关键字
*/
int[] keys;
/**
* 孩子们
*/
node[] children;
/**
* 有效关键字个数（keys 中有效 key 数目）
*/
int keynumber;
/**
* 是否是叶子节点
*/
boolean leaf = true;
/**
* 最小度数 (最小孩子数)，它决定了节点中key 的最小、最大数目，分别是 t-1 和 2t-1
*/
int t;
/**
* 构造方法（给最小度数赋值
*
* @param t 最小度数（t>=2）
*/
public node(int t) {
this.t = t;
// 最小度数*2就是最多孩子数
this.children = new node[2 * t];
this.keys = new int[2 * t - 1];
}
public node(int[] keys) {
this.keys = keys;
}
/**
* 打印有效key，为了方便调试和测试，非必须
*/
@override
public string tostring() {
return arrays.tostring(arrays.copyofrange(keys, 0, keynumber));
}
// 多路查找
node get(int key) {
int i = 0;
while (i < keynumber) {
if (keys[i] == key) {
return this;
}
if (keys[i] > key) {
break;
}
i++;
}
// 执行到此时 keys[i]>key 或 i== keynumber
if (leaf) {
return null;
}
// 非叶子情况
return children[i].get(key);
}
// 向 keys 指定索引处插入 key
void insertkey(int key, int index) {
system.arraycopy(keys, index, keys, index + 1, keynumber - index);
keys[index] = key;
keynumber++;
}
// 向 children 指定索引处插入 child
void insertchild(node child, int index) {
system.arraycopy(children, index, children, index + 1, keynumber - index);
children[index] = child;
}
}
2.1.1 实现多路查找方法get(int key)
// 多路查找
node get(int key) {
int i = 0;
while (i < keynumber) {
if (keys[i] == key) {
return this;
}
if (keys[i] > key) {
break;
}
i++;
}
// 执行到此时 keys[i]>key 或 i== keynumber
if (leaf) {
return null;
}
// 非叶子情况
return children[i].get(key);
}
2.1.2 实现插入key方法insertkey(int key, int index)
// 向 keys 指定索引处插入 key
void insertkey(int key, int index) {
system.arraycopy(keys, index, keys, index + 1, keynumber - index);
keys[index] = key;
keynumber++;
}
2.1.3 实现插入child方法insertchild(node child, int index)
// 向 children 指定索引处插入 child
void insertchild(node child, int index) {
system.arraycopy(children, index, children, index + 1, keynumber - index);
children[index] = child;
}
2.1.4 实现节点类内部工具方法
// 移除指定 index 处的 key
int removekey(int index) {
int t = keys[index];
system.arraycopy(keys, index + 1, keys, index, --keynumber - index);
return t;
}
// 移除最左边的 key
int removeleftmostkey() {
return removekey(0);
}
// 移除最右边的 key
int removerightmostkey() {
return removekey(keynumber - 1);
}
// 移除指定 index 处的 child
node removechild(int index) {
node t = children[index];
system.arraycopy(children, index + 1, children, index, keynumber - index);
children[keynumber] = null; // help gc
return t;
}
// 移除最左边的 child
node removeleftmostchild() {
return removechild(0);
}
// 移除最右边的 child
node removerightmostchild() {
return removechild(keynumber);
}
// index 孩子处左边的兄弟
node childleftsibling(int index) {
return index > 0 ? children[index - 1] : null;
}
// index 孩子处右边的兄弟
node childrightsibling(int index) {
return index == keynumber ? null : children[index + 1];
}
// 复制当前节点的所有 key 和 child 到 target
void movetotarget(node target) {
int start = target.keynumber;
if (!leaf) {
for (int i = 0; i <= keynumber; i++) {
target.children[start + i] = children[i];
}
}
for (int i = 0; i < keynumber; i++) {
target.keys[target.keynumber++] = keys[i];
}
}
2.2 b树类btree
public class btree {
final int t; // 树中节点最小度数
final int min_key_number; // 最小key数目
final int max_key_number; // 最大key数目
node root; // 根节点
public btree() {
this(2);
}
public btree(int t) {
this.t = t;
min_key_number = t - 1;
max_key_number = 2 * t - 1;
root = new node(t);
}
}
2.2.1 实现是否存在某索引方法contains(int key)
// 1. 是否存在
public boolean contains(int key) {
return root.get(key) != null;
}
2.2.2 实现新增方法put(int key)
思路：
- 首先查找本节点中的插入位置 i，如果没有空位（key 被找到），应该走更新的逻辑，目前什么没做
- 接下来分两种情况
- 如果节点是叶子节点，可以直接插入了
- 如果节点是非叶子节点，需要继续在 children[i] 处继续递归插入
- 无论哪种情况，插入完成后都可能超过节点 keys 数目限制，此时应当执行节点分裂
- 参数中的 parent 和 index 都是给分裂方法用的，代表当前节点父节点，和分裂节点是第几个孩子
判断依据为：
boolean isfull(node node) {
return node.keynumber == max_key_number;
}
代码实现：
// 2. 新增
public void put(int key) {
doput(root, key, null, 0);
}
private void doput(node node, int key, node parent, int index) {
int i = 0;
while (i < node.keynumber) {
if (node.keys[i] == key) {
return; // 更新
}
if (node.keys[i] > key) {
break; // 找到了插入位置，即为此时的 i
}
i++;
}
if (node.leaf) {
node.insertkey(key, i);
} else {
doput(node.children[i], key, node, i);
}
if (node.keynumber == max_key_number) {
split(node, parent, index);
}
}
2.2.3 实现分裂方法split(node left, node parent, int index)
分两种情况：
- 如果 parent == null 表示要分裂的是根节点，此时需要创建新根，原来的根节点作为新根的 0 孩子
- 否则
- 创建 right 节点（分裂后大于当前 left 节点的），把 t 以后的 key 和 child 都拷贝过去
- t-1 处的 key 插入到 parent 的 index 处，index 指 left 作为孩子时的索引
- right 节点作为 parent 的孩子插入到 index + 1 处
/**
* <h3>分裂方法</h3>
*
* @param left 要分裂的节点
* @param parent 分裂节点的父节点
* @param index 分裂节点是第几个孩子
*/
void split(node left, node parent, int index) {
// 分裂的是根节点
if (parent == null) {
node newroot = new node(t);
newroot.leaf = false;
newroot.insertchild(left, 0); // @todo keynumber 的维护（新节点没有孩子，应该不会有问题）
this.root = newroot;
parent = newroot;
}
// 1. 创建 right 节点，把 left 中 t 之后的 key 和 child 移动过去
node right = new node(t);
right.leaf = left.leaf;
system.arraycopy(left.keys, t, right.keys, 0, t - 1);
// 分裂节点是非叶子的情况
if (!left.leaf) {
system.arraycopy(left.children, t, right.children, 0, t);
for (int i = t; i <= left.keynumber; i++) {
left.children[i] = null;
}
}
right.keynumber = t - 1;
left.keynumber = t - 1;
// 2. 中间的 key （t-1 处）插入到父节点
int mid = left.keys[t - 1];
parent.insertkey(mid, index);
// 3. right 节点作为父节点的孩子
parent.insertchild(right, index + 1);
}
2.2.4 实现删除方法remove(int key)
注意本删除方法是删除b树中某个节点的某个key，不是把整个节点删了
主要分为以下情况：
case 1：当前节点是叶子节点，没找到，直接返回
case 2：当前节点是叶子节点，找到，因为是叶子节点，所以直接删
case 3：当前节点是非叶子节点，没找到，要继续到孩子节点查找
case 4：当前节点是非叶子节点，找到，再接着找到其后继key，替换被删除节点，然后删除后继key
case 5：删除后 key 数目 < 下限 [ t - 1 ]（不平衡），进行平衡性调整（具体见 2.2.4）
case 6：根节点
// 3. 删除
public void remove(int key) {
doremove(null, root, 0, key);
}
private void doremove(node parent, node node, int index, int key) {
int i = 0;
while (i < node.keynumber) {
if (node.keys[i] >= key) {
break;
}
i++;
}
// i 找到：代表待删除 key 的索引
// i 没找到： 代表到第i个孩子继续查找
if (node.leaf) {
if (!found(node, key, i)) { // case1
return;
} else { // case2
node.removekey(i);
}
} else {
if (!found(node, key, i)) { // case3
doremove(node, node.children[i], i, key);
} else { // case4
// 1. 找到后继 key
node s = node.children[i + 1];
while (!s.leaf) {
s = s.children[0];
}
int skey = s.keys[0];
// 2. 替换待删除 key
node.keys[i] = skey;
// 3. 删除后继 key
doremove(node, node.children[i + 1], i + 1, skey);
}
}
if (node.keynumber < min_key_number) {
// 调整平衡 case 5 case 6
balance(parent, node, index);
}
}
2.2.4 实现平衡方法balance(node parent, node x, int i)
删除后平衡主要分为以下情况：
case 5-1：左边富裕，右旋
case 5-2：右边富裕，左旋
case 5-3：两边都不够借，向左合并
2.2.4.1 右旋
一颗平衡的b树，如下
4
/ \
1,2,3 5,6
删除key 5后变为
4
/ \
1,2,3 6
此时节点6的key的数目小于下限，为了让节点6平衡，需要对key的数目+1，此时左边兄弟的节点富裕，所以可以通过右旋保持平衡
1️⃣ 先把父节点4旋转下去，如下
4
/ \
1,2,3 4,6
2️⃣ 再把左边兄弟节点的3旋转上去，b树恢复平衡，如下
3
/ \
1,2 4,6
2.2.4.2 左旋
一颗平衡的b树，如下
3
/ \
1,2 4,5,6
删除key 1后变为
3
/ \
2 4,5,6
此时节点2的key的数目小于下限，为了让节点2平衡，需要对key的数目+1，此时右边兄弟的节点富裕，所以可以通过左旋保持平衡
1️⃣ 先把父节点3旋转下去，如下
3
/ \
2,3 4,5,6
2️⃣ 再把右边兄弟节点的4旋转上去，b树恢复平衡，如下
4
/ \
2,3 5,6
2.2.4.3 合并
一颗平衡的b树，如下
3
/ \
1,2 4,5
删除key 4后变为
3
/ \
1,2 5
此时节点5的key的数目小于下限，为了让节点5平衡，需要对key的数目+1。但此时左边或右边的兄弟节点并不富裕，不能通过旋转的方式重新平衡，所以这类情况要使用合并（向左合并）
1️⃣ 先把父节点3合并到最右边，如下
null
/ \
1,2,3 5
2️⃣ 再把右边的兄弟节点元素合并到最右边，如下
null
/
1,2,3,5
3️⃣ 最后把0号孩子替换根节点，如下
1,2,3,5
2.2.4.4 代码实现
// 平衡
private void balance(node parent, node x, int i) {
// case 6 根节点
if (x == root) {
if (root.keynumber == 0 && root.children[0] != null) {
root = root.children[0];
}
return;
}
node left = parent.childleftsibling(i);
node right = parent.childrightsibling(i);
// case 5-1 左边富裕，右旋
if (left != null && left.keynumber > min_key_number) {
// a) 父节点中前驱key旋转下来
x.insertkey(parent.keys[i - 1], 0);
if (!left.leaf) {
// b) left中最大的孩子换爹
x.insertchild(left.removerightmostchild(), 0);
}
// c) left中最大的key旋转上去
parent.keys[i - 1] = left.removerightmostkey();
return;
}
// case 5-2 右边富裕，左旋
if (right != null && right.keynumber > min_key_number) {
// a) 父节点中后继key旋转下来
x.insertkey(parent.keys[i], x.keynumber);
// b) right中最小的孩子换爹
if (!right.leaf) {
x.insertchild(right.removeleftmostchild(), x.keynumber);
}
// c) right中最小的key旋转上去
parent.keys[i] = right.removeleftmostkey();
return;
}
// case 5-3 两边都不够借，向左合并
if (left != null) {
// 向左兄弟合并
parent.removechild(i);
left.insertkey(parent.removekey(i - 1), left.keynumber);
x.movetotarget(left);
} else {
// 向自己合并
parent.removechild(i + 1);
x.insertkey(parent.removekey(i), x.keynumber);
right.movetotarget(x);
}
}
3 b树java实现代码完整版（复制粘贴用）
import java.util.arrays;
/**
* <h3>b-树</h3>
*/
@suppresswarnings("all")
public class btree {
static class node {
/**
* 关键字
*/
int[] keys;
/**
* 孩子们
*/
node[] children;
/**
* 有效关键字个数（keys 中有效 key 数目）
*/
int keynumber;
/**
* 是否是叶子节点
*/
boolean leaf = true;
/**
* 最小度数 (最小孩子数)，它决定了节点中key 的最小、最大数目，分别是 t-1 和 2t-1
*/
int t;
/**
* 构造方法（给最小度数赋值
*
* @param t 最小度数（t>=2）
*/
public node(int t) {
this.t = t;
// 最小度数*2就是最多孩子数
this.children = new node[2 * t];
this.keys = new int[2 * t - 1];
}
public node(int[] keys) {
this.keys = keys;
}
/**
* 打印有效key，为了方便调试和测试，非必须
*/
@override
public string tostring() {
return arrays.tostring(arrays.copyofrange(keys, 0, keynumber));
}
// 多路查找
node get(int key) {
int i = 0;
while (i < keynumber) {
if (keys[i] == key) {
return this;
}
if (keys[i] > key) {
break;
}
i++;
}
// 执行到此时 keys[i]>key 或 i== keynumber
if (leaf) {
return null;
}
// 非叶子情况
return children[i].get(key);
}
// 向 keys 指定索引处插入 key
void insertkey(int key, int index) {
system.arraycopy(keys, index, keys, index + 1, keynumber - index);
keys[index] = key;
keynumber++;
}
// 向 children 指定索引处插入 child
void insertchild(node child, int index) {
system.arraycopy(children, index, children, index + 1, keynumber - index);
children[index] = child;
}
// 移除指定 index 处的 key
int removekey(int index) {
int t = keys[index];
system.arraycopy(keys, index + 1, keys, index, --keynumber - index);
return t;
}
// 移除最左边的 key
int removeleftmostkey() {
return removekey(0);
}
// 移除最右边的 key
int removerightmostkey() {
return removekey(keynumber - 1);
}
// 移除指定 index 处的 child
node removechild(int index) {
node t = children[index];
system.arraycopy(children, index + 1, children, index, keynumber - index);
children[keynumber] = null; // help gc
return t;
}
// 移除最左边的 child
node removeleftmostchild() {
return removechild(0);
}
// 移除最右边的 child
node removerightmostchild() {
return removechild(keynumber);
}
// index 孩子处左边的兄弟
node childleftsibling(int index) {
return index > 0 ? children[index - 1] : null;
}
// index 孩子处右边的兄弟
node childrightsibling(int index) {
return index == keynumber ? null : children[index + 1];
}
// 复制当前节点的所有 key 和 child 到 target
void movetotarget(node target) {
int start = target.keynumber;
if (!leaf) {
for (int i = 0; i <= keynumber; i++) {
target.children[start + i] = children[i];
}
}
for (int i = 0; i < keynumber; i++) {
target.keys[target.keynumber++] = keys[i];
}
}
}
final int t; // 树中节点最小度数
final int min_key_number; // 最小key数目
final int max_key_number; // 最大key数目
node root; // 根节点
public btree() {
// 最小度数默认是2
this(2);
}
public btree(int t) {
this.t = t;
root = new node(t);
max_key_number = 2 * t - 1;
min_key_number = t - 1;
}
// 1. 是否存在
public boolean contains(int key) {
return root.get(key) != null;
}
// 2. 新增
public void put(int key) {
doput(root, key, null, 0);
}
private void doput(node node, int key, node parent, int index) {
int i = 0;
while (i < node.keynumber) {
if (node.keys[i] == key) {
return; // 更新
}
if (node.keys[i] > key) {
break; // 找到了插入位置，即为此时的 i
}
i++;
}
if (node.leaf) {
node.insertkey(key, i);
} else {
doput(node.children[i], key, node, i);
}
if (node.keynumber == max_key_number) {
split(node, parent, index);
}
}
/**
* <h3>分裂方法</h3>
*
* @param left 要分裂的节点
* @param parent 分裂节点的父节点
* @param index 分裂节点是第几个孩子
*/
void split(node left, node parent, int index) {
// 分裂的是根节点
if (parent == null) {
node newroot = new node(t);
newroot.leaf = false;
newroot.insertchild(left, 0); // @todo keynumber 的维护（新节点没有孩子，应该不会有问题）
this.root = newroot;
parent = newroot;
}
// 1. 创建 right 节点，把 left 中 t 之后的 key 和 child 移动过去
node right = new node(t);
right.leaf = left.leaf;
system.arraycopy(left.keys, t, right.keys, 0, t - 1);
// 分裂节点是非叶子的情况
if (!left.leaf) {
system.arraycopy(left.children, t, right.children, 0, t);
for (int i = t; i <= left.keynumber; i++) {
left.children[i] = null;
}
}
right.keynumber = t - 1;
left.keynumber = t - 1;
// 2. 中间的 key （t-1 处）插入到父节点
int mid = left.keys[t - 1];
parent.insertkey(mid, index);
// 3. right 节点作为父节点的孩子
parent.insertchild(right, index + 1);
}
// 3. 删除
public void remove(int key) {
doremove(null, root, 0, key);
}
private void doremove(node parent, node node, int index, int key) {
int i = 0;
while (i < node.keynumber) {
if (node.keys[i] >= key) {
break;
}
i++;
}
// i 找到：代表待删除 key 的索引
// i 没找到： 代表到第i个孩子继续查找
if (node.leaf) {
if (!found(node, key, i)) { // case1
return;
} else { // case2
node.removekey(i);
}
} else {
if (!found(node, key, i)) { // case3
doremove(node, node.children[i], i, key);
} else { // case4
// 1. 找到后继 key
node s = node.children[i + 1];
while (!s.leaf) {
s = s.children[0];
}
int skey = s.keys[0];
// 2. 替换待删除 key
node.keys[i] = skey;
// 3. 删除后继 key
doremove(node, node.children[i + 1], i + 1, skey);
}
}
if (node.keynumber < min_key_number) {
// 调整平衡 case 5 case 6
balance(parent, node, index);
}
}
// 平衡
private void balance(node parent, node x, int i) {
// case 6 根节点
if (x == root) {
if (root.keynumber == 0 && root.children[0] != null) {
root = root.children[0];
}
return;
}
node left = parent.childleftsibling(i);
node right = parent.childrightsibling(i);
// case 5-1 左边富裕，右旋
if (left != null && left.keynumber > min_key_number) {
// a) 父节点中前驱key旋转下来
x.insertkey(parent.keys[i - 1], 0);
if (!left.leaf) {
// b) left中最大的孩子换爹
x.insertchild(left.removerightmostchild(), 0);
}
// c) left中最大的key旋转上去
parent.keys[i - 1] = left.removerightmostkey();
return;
}
// case 5-2 右边富裕，左旋
if (right != null && right.keynumber > min_key_number) {
// a) 父节点中后继key旋转下来
x.insertkey(parent.keys[i], x.keynumber);
// b) right中最小的孩子换爹
if (!right.leaf) {
x.insertchild(right.removeleftmostchild(), x.keynumber);
}
// c) right中最小的key旋转上去
parent.keys[i] = right.removeleftmostkey();
return;
}
// case 5-3 两边都不够借，向左合并
if (left != null) {
// 向左兄弟合并
parent.removechild(i);
left.insertkey(parent.removekey(i - 1), left.keynumber);
x.movetotarget(left);
} else {
// 向自己合并
parent.removechild(i + 1);
x.insertkey(parent.removekey(i), x.keynumber);
right.movetotarget(x);
}
}
private boolean found(node node, int key, int i) {
return i < node.keynumber && node.keys[i] == key;
}
// 遍历树结构并打印节点的键值
public void travel() {
dotravel(root);
}
public void dotravel(node node) {
if (node == null) {
return;
}
int i = 0;
for (; i < node.keynumber; i++) {
dotravel(node.children[i]);
system.out.println(node.keys[i]);
}
dotravel(node.children[i]);
}
}
如果觉得这篇文章对您有所帮助的话，请动动小手点波关注💗，你的点赞👍收藏⭐️转发🔗评论📝都是对博主最好的支持~
发表评论