B树的特点
多路平衡查找树定义m（一般大于2）为树的阶，表示节点最大的分枝数量，限制节点最大的元素数量为m-1所有叶子节点深度相同其他…
B树的构建与二叉搜索树类似。 由于存在元素数量的限制，因此需要在添加元素后检查节点是否需要进行分裂操作，分裂操作会向父节点添加元素。 所有叶子节点深度相同个人认为两个操作保证。第一个操作是节点元素数量达到最大之后的分裂操作，分裂操作要么增加深度（分裂节点不存在父节点或者父节点也需要分裂），要么不改变深度（存在父节点且不需要分裂）。第二个操作是在删除元素时对树的调整（删除元素时，如果父节点需要和子节点合并组成新节点，必会造成对应分支的深度减小，此时需要将新节点合并到相邻的节点，维持叶节点深度相同的特性）。
主要实现流程设计
根据本文B树的特点，对B树进行代码设计并实现。完整代码在文末提供。
分裂操作 删除操作
代码实现
代码实现依照本文的实现流程设计，主要功能包括树的构建，插入操作和删除操作，以及元素搜索等附加操作。
节点定义
class BTreeNode {
// 阶数
int m;
// 父节点
public BTreeNode parent;
// 数据域
// 0 < data.length < m
List<Object> data;
// 指针域
// point.length = m
List<BTreeNode> point;
BTreeNode(int m) {
this.m = m;
data = new ArrayList<>(m);
point = new ArrayList<>(m);
parent = null;
}
}
元素插入
// 插入数据
public BTreeNode insert(BTreeNode root, T t){
// 元素个数少于m，直接插入
int index = 0;
while(root != null){
index = 0;
// 确定元素插入位置
for(int i = 0; i < root.data.size(); i++){
if(t.compareTo(root.data.get(i)) > 0){
index = i + 1;
}
}
// 元素下沉
if(root.point.size() > index && root.point.get(index) != null){
root = root.point.get(index);
}else{// 没有子节点，即叶节点
break;
}
}
// 树的高度增加来自底层节点的向上分裂，并且每次分裂的开始是从叶节点开始
// 插入到节点数组中
root.data.add(index, t);
// 检查该节点是否需要分裂
root = splitTreeNode(root);
// 返回树的根节点
while(root.parent != null){
root = root.parent;
}
return root;
}
节点分裂操作
// 分裂节点
public BTreeNode splitTreeNode(BTreeNode root){
int index = 0;
while(root.data.size() >= m) {
// 分裂点数据
index = root.data.size() / 2;
Object splitData = root.data.get(index);
// 节点分裂
BTreeNode leftNode = new BTreeNode(m);
BTreeNode rightNode = new BTreeNode(m);
copyKey(root, leftNode, 0, index - 1);
copyPoint(root, leftNode, 0, index);
copyKey(root, rightNode, index + 1, root.data.size() - 1);
copyPoint(root, rightNode, index + 1, root.point.size() - 1);
if (root.parent == null) {// 分裂成新的父节点，树高度增加
BTreeNode parentNode2 = new BTreeNode(m);
parentNode2.data.add(splitData);
leftNode.parent = parentNode2;
rightNode.parent = parentNode2;
// 原本子节点的父节点指向新的分裂节点
for (int i = 0; i < leftNode.point.size(); i++) {
leftNode.point.get(i).parent = leftNode;
}
for (int i = 0; i < rightNode.point.size(); i++) {
rightNode.point.get(i).parent = rightNode;
}
// 合并分裂节点到父节点
mergePoint(0, leftNode, rightNode, parentNode2);
root = parentNode2;
} else {// 已有父节点，直接插入
// 确定在父节点中的插入位置
index = 0;
for (int i = 0; i < root.parent.data.size(); i++) {
if (((Comparable) splitData).compareTo(root.parent.data.get(i)) > 0) {
index = i + 1;
}
}
root.parent.data.add(index, splitData);
// 父节点原本指向当前节点的指针去掉
int prePoint = 0;
for (int i = 0; i < root.parent.point.size(); i++) {
if (root.parent.point.get(i) == root) {
prePoint = i;
break;
}
}
root.parent.point.remove(prePoint);
// 原本子节点的父节点指向新的分裂节点
for (int i = 0; i < leftNode.point.size(); i++) {
leftNode.point.get(i).parent = leftNode;
}
for (int i = 0; i < rightNode.point.size(); i++) {
rightNode.point.get(i).parent = rightNode;
}
leftNode.parent = root.parent;
rightNode.parent = root.parent;
// 合并分裂节点到父节点
mergePoint(index, leftNode, rightNode, root.parent);
}
// 向上检查，检查父节点是否满足分裂条件
if (root.parent == null) {
return root;
//break;
} else {
root = root.parent;
}
}
return root;
}
元素删除
// B树删除K操作
// 1、叶子节点上，如果删除后节点key数量大于等于1,直接删除操作结束
// 2、叶子节点上，如果删除后节点key数量等于0,需要从父节点借元素，兄弟节点的元素移到父节点中
// 如果兄弟节点的key数量被借后等于0，则需要合并节点，减少分支树
// 3、如果在非叶子节点上，则将后继填充到删除位置，然后重复1,2删除后继
public BTreeNode delete(BTreeNode root, Object t){
BTreeNode tempRoot = root;
BTreeNode targetNode = search(tempRoot, t);
if(targetNode == null){// 不存在K
return root;
}
if(root == targetNode && targetNode.data.size() == 1 && targetNode.point.size() == 0){// 只有一个值了
targetNode.data.remove(t);
return root;
}
// 非叶子节点，删除后继节点，删除后继节点等于删除叶子节点
BTreeNode successor = null;
// 删除操作：2.a
if(targetNode.point.size() != 0) {
successor = successor(root, t);
// 交换值
if (successor != null) {
// 交换值
Object tempData = successor.data.get(0);
successor.data.set(0, t);
int index = 0;
for (int i = 0; i < targetNode.data.size(); i++){
if(targetNode.data.get(i).equals(t)){
index = i;
break;
}
}
targetNode.data.set(index, tempData);
targetNode = successor;
//t = tempData;
}
}// 转换为删除叶子节点上的数据
//else{// 删除叶子节点上的数据
{ // 直接删除|借位|合并
if(targetNode.data.size() > 1){
// 删除操作：1.a
// 可直接删除
targetNode.data.remove(t);
}else{
// 借位：把借的数据移到父节点，父节点下沉一个数据到待删除节点
BTreeNode renderNode = null;
// 删除操作：1.b
if((renderNode = renderBrotherNode(targetNode, "left")) != null){
// 借左节点中的数据，借最后一个
Object renderData = renderNode.data.get(renderNode.data.size() - 1);
// 父节点借位data的下标
int index = 0;
for(int i= 0; i < renderNode.parent.point.size(); i++){
if(renderNode.parent.point.get(i) == renderNode){
index = i;
}
}
// 父节点数据下沉到待删除节点
targetNode.data.set(0, renderNode.parent.data.get(index));
// 借位数据上移到父节点
renderNode.parent.data.set(index, renderData);
// 删除借位节点的数据
renderNode.data.remove(renderNode.data.size() - 1);
// 删除操作：1.b
}else if((renderNode = renderBrotherNode(targetNode, "right")) != null){
// 借右节点中的数据，借第一个
Object renderData = renderNode.data.get(0);
// 父节点借位data的下标
int index = 0;
for(int i= 0; i < renderNode.parent.point.size(); i++){
if(renderNode.parent.point.get(i) == renderNode){
index = i - 1;
}
}
// 父节点数据下沉到待删除节点
targetNode.data.set(0, renderNode.parent.data.get(index));
// 借位数据上移到父节点
renderNode.parent.data.set(index, renderData);
// 删除借位节点的数据
renderNode.data.remove(0);
// 删除操作：1.c
} else{// 左右节点和父节点的数据都为1，合并数据。如果从父节点借数据也是必合并，因为原本的指向删除节点的point对应的data变为了空
// 指向待删除节点的指针
int index = 0;
for(int i= 0; i < targetNode.parent.point.size(); i++){
if(targetNode.parent.point.get(i) == targetNode){
index = i;// 指向待删除节点的指针
}
}
// 待删除节点的父节点
BTreeNode parentNode = targetNode.parent;
if(index + 1 == targetNode.parent.point.size()){
// 向左合并
targetNode.parent.point.get(index - 1).data.add(targetNode.parent.data.get(index - 1));
// 移除多余的值和指针
targetNode.parent.data.remove(index - 1);
targetNode.parent.point.remove(index);
}else{
// 默认向右合并
targetNode.parent.point.get(index + 1).data.add(0, targetNode.parent.data.get(index));
// 移除多余的值和指针
targetNode.parent.data.remove(index);
targetNode.parent.point.remove(index);
}
// 删除操作：1.d
// 需要向上合并
while(parentNode.data.size() == 0){
// 根节点
// if(parentNode.parent == null || parentNode.parent.data.size() == 0){
if(parentNode.parent == null){
root = parentNode.point.get(0);
root.parent = null;
break;
}
index = 0;
for(int i= 0; i < parentNode.parent.point.size(); i++){
if(parentNode.parent.point.get(i) == parentNode){
index = i;// 指向待删除节点的指针
}
}
BTreeNode newNode = new BTreeNode(m);
newNode.data.addAll(parentNode.point.get(0).data);
newNode.point.addAll(parentNode.point.get(0).point);
BTreeNode mergeNode = null;
if(index + 1 == parentNode.parent.point.size() && index != 0){
parentNode.parent.point.get(index - 1).data.add(parentNode.parent.data.get(index - 1));
newNode.parent = parentNode.parent.point.get(index - 1);
parentNode.parent.data.remove(index - 1);
parentNode.parent.point.remove(index);
parentNode.parent.point.get(index - 1).point.add(newNode);
mergeNode = parentNode.parent.point.get(index - 1);
}else{
parentNode.parent.point.get(index + 1).data.add(0, parentNode.parent.data.get(index));
newNode.parent = parentNode.parent.point.get(index + 1);
parentNode.parent.data.remove(index);
parentNode.parent.point.remove(index);
parentNode.parent.point.get(index).point.add(0, newNode);
mergeNode = parentNode.parent.point.get(index);
}
// 修改父结点指针
for (int i = 0; i < newNode.point.size(); i++){
newNode.point.get(i).parent = newNode;
}
// 检查合并后的节点是否需要向上分裂
splitTreeNode(mergeNode);
parentNode = parentNode.parent;
}
}
}
}
return root;
}
完整代码
class BTreeNode {
// 阶数
int m;
// 父节点
public BTreeNode parent;
// 数据域
// 0 < data.length < m
List<Object> data;
// 指针域
// point.length = m
List<BTreeNode> point;
BTreeNode(int m) {
this.m = m;
data = new ArrayList<>(m);
point = new ArrayList<>(m);
parent = null;
}
}
public class BTree<T extends Comparable> {
// 树的阶数
static int m = 7;
public BTreeNode init(T[] t){
BTreeNode root = new BTreeNode(m);
for(int i = 0; i < t.length; i++){
root = insert(root, t[i]);
}
return root;
}
// 插入数据
public BTreeNode insert(BTreeNode root, T t){
// 元素个数少于m，直接插入
int index = 0;
while(root != null){
index = 0;
// 确定元素插入位置
for(int i = 0; i < root.data.size(); i++){
if(t.compareTo(root.data.get(i)) > 0){
index = i + 1;
}
}
// 元素下沉
if(root.point.size() > index && root.point.get(index) != null){
root = root.point.get(index);
}else{// 没有子节点，即叶节点
break;
}
}
// 树的高度增加来自底层节点的向上分裂，并且每次分裂的开始是从叶节点开始
// 插入到节点数组中
root.data.add(index, t);
// 检查该节点是否需要分裂
root = splitTreeNode(root);
// 返回树的根节点
while(root.parent != null){
root = root.parent;
}
return root;
}
// 分裂出左节点
public void copyKey(BTreeNode srcNode, BTreeNode dstNode, int start, int end){
//System.arraycopy(srcNode.data, start, dstNode.data, 0, end - start + 1);
for(int i = start; i <= end; i++){
dstNode.data.add(srcNode.data.get(i));
}
}
// 分裂出右节点
public void copyPoint(BTreeNode srcNode, BTreeNode dstNode, int start, int end){
//System.arraycopy(srcNode.point, start, dstNode.point, 0, end - start + 1);
if(srcNode.point.size() < 1)
return;
for(int i = start; i <= end; i++){
dstNode.point.add(srcNode.point.get(i));
}
}
// 合并到父节点
public void mergePoint(int index, BTreeNode leftNode, BTreeNode rightNode, BTreeNode parentNode){
parentNode.point.add(index, leftNode);
parentNode.point.add(index + 1, rightNode);
}
// B树删除K操作
// 1、叶子节点上，如果删除后节点key数量大于等于1,直接删除操作结束
// 2、叶子节点上，如果删除后节点key数量等于0,需要从父节点借元素，兄弟节点的元素移到父节点中
// 如果兄弟节点的key数量被借后等于0，则需要合并节点，减少分支树
// 3、如果在非叶子节点上，则将后继填充到删除位置，然后重复1,2删除后继
public BTreeNode delete(BTreeNode root, Object t){
BTreeNode tempRoot = root;
BTreeNode targetNode = search(tempRoot, t);
if(targetNode == null){// 不存在K
return root;
}
if(root == targetNode && targetNode.data.size() == 1 && targetNode.point.size() == 0){// 只有一个值了
targetNode.data.remove(t);
return root;
}
// 非叶子节点，删除后继节点，删除后继节点等于删除叶子节点
BTreeNode successor = null;
if(targetNode.point.size() != 0) {
successor = successor(root, t);
// 交换值
if (successor != null) {
// 交换值
Object tempData = successor.data.get(0);
successor.data.set(0, t);
int index = 0;
for (int i = 0; i < targetNode.data.size(); i++){
if(targetNode.data.get(i).equals(t)){
index = i;
break;
}
}
targetNode.data.set(index, tempData);
targetNode = successor;
//t = tempData;
}
}// 转换为删除叶子节点上的数据
//else{// 删除叶子节点上的数据
{ // 直接删除|借位|合并
if(targetNode.data.size() > 1){
// 可直接删除
targetNode.data.remove(t);
}else{
// 借位：把借的数据移到父节点，父节点下沉一个数据到待删除节点
BTreeNode renderNode = null;
if((renderNode = renderBrotherNode(targetNode, "left")) != null){
// 借左节点中的数据，借最后一个
Object renderData = renderNode.data.get(renderNode.data.size() - 1);
// 父节点借位data的下标
int index = 0;
for(int i= 0; i < renderNode.parent.point.size(); i++){
if(renderNode.parent.point.get(i) == renderNode){
index = i;
}
}
// 父节点数据下沉到待删除节点
targetNode.data.set(0, renderNode.parent.data.get(index));
// 借位数据上移到父节点
renderNode.parent.data.set(index, renderData);
// 删除借位节点的数据
renderNode.data.remove(renderNode.data.size() - 1);
}else if((renderNode = renderBrotherNode(targetNode, "right")) != null){
// 借右节点中的数据，借第一个
Object renderData = renderNode.data.get(0);
// 父节点借位data的下标
int index = 0;
for(int i= 0; i < renderNode.parent.point.size(); i++){
if(renderNode.parent.point.get(i) == renderNode){
index = i - 1;
}
}
// 父节点数据下沉到待删除节点
targetNode.data.set(0, renderNode.parent.data.get(index));
// 借位数据上移到父节点
renderNode.parent.data.set(index, renderData);
// 删除借位节点的数据
renderNode.data.remove(0);
} else{// 左右节点和父节点的数据都为1，合并数据。如果从父节点借数据也是必合并，因为原本的指向删除节点的point对应的data变为了空
// 指向待删除节点的指针
int index = 0;
for(int i= 0; i < targetNode.parent.point.size(); i++){
if(targetNode.parent.point.get(i) == targetNode){
index = i;// 指向待删除节点的指针
}
}
// 待删除节点的父节点
BTreeNode parentNode = targetNode.parent;
if(index + 1 == targetNode.parent.point.size()){
// 向左合并
targetNode.parent.point.get(index - 1).data.add(targetNode.parent.data.get(index - 1));
// 移除多余的值和指针
targetNode.parent.data.remove(index - 1);
targetNode.parent.point.remove(index);
}else{
// 默认向右合并
targetNode.parent.point.get(index + 1).data.add(0, targetNode.parent.data.get(index));
// 移除多余的值和指针
targetNode.parent.data.remove(index);
targetNode.parent.point.remove(index);
}
// 需要向上合并
while(parentNode.data.size() == 0){
// 根节点
// if(parentNode.parent == null || parentNode.parent.data.size() == 0){
if(parentNode.parent == null){
root = parentNode.point.get(0);
root.parent = null;
break;
}
index = 0;
for(int i= 0; i < parentNode.parent.point.size(); i++){
if(parentNode.parent.point.get(i) == parentNode){
index = i;// 指向待删除节点的指针
}
}
BTreeNode newNode = new BTreeNode(m);
newNode.data.addAll(parentNode.point.get(0).data);
newNode.point.addAll(parentNode.point.get(0).point);
BTreeNode mergeNode = null;
if(index + 1 == parentNode.parent.point.size() && index != 0){
parentNode.parent.point.get(index - 1).data.add(parentNode.parent.data.get(index - 1));
newNode.parent = parentNode.parent.point.get(index - 1);
parentNode.parent.data.remove(index - 1);
parentNode.parent.point.remove(index);
parentNode.parent.point.get(index - 1).point.add(newNode);
mergeNode = parentNode.parent.point.get(index - 1);
}else{
parentNode.parent.point.get(index + 1).data.add(0, parentNode.parent.data.get(index));
newNode.parent = parentNode.parent.point.get(index + 1);
parentNode.parent.data.remove(index);
parentNode.parent.point.remove(index);
parentNode.parent.point.get(index).point.add(0, newNode);
mergeNode = parentNode.parent.point.get(index);
}
// 修改父结点指针
for (int i = 0; i < newNode.point.size(); i++){
newNode.point.get(i).parent = newNode;
}
// 检查合并后的节点是否需要向上分裂
splitTreeNode(mergeNode);
parentNode = parentNode.parent;
}
}
}
}
return root;
}
// 分裂节点
public BTreeNode splitTreeNode(BTreeNode root){
int index = 0;
while(root.data.size() >= m) {
// 分裂点数据
index = root.data.size() / 2;
Object splitData = root.data.get(index);
// 节点分裂
BTreeNode leftNode = new BTreeNode(m);
BTreeNode rightNode = new BTreeNode(m);
copyKey(root, leftNode, 0, index - 1);
copyPoint(root, leftNode, 0, index);
copyKey(root, rightNode, index + 1, root.data.size() - 1);
copyPoint(root, rightNode, index + 1, root.point.size() - 1);
if (root.parent == null) {// 分裂成新的父节点，树高度增加
BTreeNode parentNode2 = new BTreeNode(m);
parentNode2.data.add(splitData);
leftNode.parent = parentNode2;
rightNode.parent = parentNode2;
// 原本子节点的父节点指向新的分裂节点
for (int i = 0; i < leftNode.point.size(); i++) {
leftNode.point.get(i).parent = leftNode;
}
for (int i = 0; i < rightNode.point.size(); i++) {
rightNode.point.get(i).parent = rightNode;
}
// 合并分裂节点到父节点
mergePoint(0, leftNode, rightNode, parentNode2);
root = parentNode2;
} else {// 已有父节点，直接插入
// 确定在父节点中的插入位置
index = 0;
for (int i = 0; i < root.parent.data.size(); i++) {
if (((Comparable) splitData).compareTo(root.parent.data.get(i)) > 0) {
index = i + 1;
}
}
root.parent.data.add(index, splitData);
// 父节点原本指向当前节点的指针去掉
int prePoint = 0;
for (int i = 0; i < root.parent.point.size(); i++) {
if (root.parent.point.get(i) == root) {
prePoint = i;
break;
}
}
root.parent.point.remove(prePoint);
// 原本子节点的父节点指向新的分裂节点
for (int i = 0; i < leftNode.point.size(); i++) {
leftNode.point.get(i).parent = leftNode;
}
for (int i = 0; i < rightNode.point.size(); i++) {
rightNode.point.get(i).parent = rightNode;
}
leftNode.parent = root.parent;
rightNode.parent = root.parent;
// 合并分裂节点到父节点
mergePoint(index, leftNode, rightNode, root.parent);
}
// 向上检查，检查父节点是否满足分裂条件
if (root.parent == null) {
return root;
//break;
} else {
root = root.parent;
}
}
return root;
}
// 能否从兄弟节点借数据。如果可以，返回兄弟节点
public BTreeNode renderBrotherNode(BTreeNode root, String type){
// 没有父节点
BTreeNode parent = root.parent;
if(parent == null){
return null;
}
int i = 0;
while(i < parent.point.size()){
if(root.parent.point.get(i) == root){
break;
}
i++;
}
if(i >= parent.point.size()){
return null;
}
BTreeNode brotherNode = null;
switch (type){
case "left":{
if(i == 0)return null;
brotherNode = parent.point.get(i - 1);
}break;
case "right":{
if(i + 1 >= parent.point.size()){
return null;
}
brotherNode = parent.point.get(i + 1);
}break;
default: return null;
}
if(brotherNode != null && brotherNode.data.size() > 1){
return brotherNode;
}
return null;
}
// 查找某个数据，并返回所在的节点
public BTreeNode search(BTreeNode root, Object t){
while(root != null){
int i = 0;
boolean flag = true;
for(i = 0; i < root.data.size(); i++){
if(((Comparable)t).compareTo(root.data.get(i)) == 0){// 存在
return root;
}else if(((Comparable)t).compareTo(root.data.get(i)) < 0){// 当前值大于t
if(root.point.size() > i){
root = root.point.get(i);
flag = false;
break;
}else{
return null;
}
}else{// 当前值小于t
continue;
}
}
if(flag && i == root.data.size()){
if(root.point.size() - 1 == i){
root = root.point.get(i);
}else if(root.point.size() < i){
return null;
}
}
}
return null;
}
// 查找K的前驱节点
// 如果存在前驱节点，前驱K一定是节点中的最后一个K
public BTreeNode precursor(BTreeNode root, Object k){
return null;
}
// 查找K的后继节点
// 如果存在后继节点，后继K一定是节点中的第一个K。或者只存在一个节点时，后继为顺序节点
public BTreeNode successor(BTreeNode root, Object k){
BTreeNode tempRoot = root;
BTreeNode node = new BTree<>().search(tempRoot, k);
if(k == null){
return null;
}
int i = 0;
while(i < node.data.size()){
if(k.equals(node.data.get(i))){
i++;
break;
}
i++;
}
// 非单节点，但是单节点应该不会在这里出现
if(node.point.size() != 0){
node= node.point.get(i);
while(node.point.size() != 0){
node= node.point.get(0);
}
}
return node;
}
// 随机生成数据添加与删除测试
public static Map<String, List<Integer>> generateRandomData(int len){
HashMap<String, List<Integer>> result = new HashMap<>();
List<Integer> insert = new ArrayList<>(len);
List<Integer> delete = new ArrayList<>(len);
List<Integer> data = new ArrayList<>(len);
List<Integer> data2 = new ArrayList<>(len);
int tempLen = len;
while (tempLen > 0){
data.add(tempLen);
data2.add(tempLen);
tempLen--;
}
int index = 0;
while (tempLen < len){
index = new Random().nextInt(data.size());
insert.add(data.get(index));
data.remove(index);
tempLen++;
}
while (tempLen > 0){
index = new Random().nextInt(data2.size());
delete.add(data2.get(index));
data2.remove(index);
tempLen--;
}
result.put("insert", insert);
result.put("delete", delete);
return result;
}
// 测试
public static void main(String[] args){
// Integer[] data = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
// Integer[] data = new Integer[]{39, 22, 97, 41, 53, 13, 21, 40, 30, 27, 33, 36, 35, 34, 24, 29, 26, 17, 28, 29, 31, 32};
// Integer[] data = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
// Integer[] data = new Integer[]{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 71, 72};
// Integer[] data = new Integer[]{39, 22, 97, 41, 53, 13, 21, 40, 30, 27, 33, 36, 35, 34, 24, 29, 26};
// 创建B-树
//BTreeNode root = new BTree<Integer>().init(data);
//BTreeNode node = new BTree<Integer>().search(root, 33);
//BTreeNode successorNode = new BTree<>().successor(root, 28);
// BTreeNode root2 = new BTree<>().delete(root, 12);
// 删除叶节点数据-Integer[] data = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
// root = new BTree<>().delete(root, 11);
// root = new BTree<>().delete(root, 10);
// root = new BTree<>().delete(root, 9);
// root = new BTree<>().delete(root, 8);
// root = new BTree<>().delete(root, 7);
// root = new BTree<>().delete(root, 6);
// root = new BTree<>().delete(root, 5);
// root = new BTree<>().delete(root, 4);
// root = new BTree<>().delete(root, 3);
// root = new BTree<>().delete(root, 2);
// root = new BTree<>().delete(root, 1);
// 删除非叶子节点数据
// root = new BTree<>().delete(root, 8);
// root = new BTree<>().delete(root, 4);
// root = new BTree<>().delete(root, 9);
// root = new BTree<>().delete(root, 2);
// 删除非叶子节点数据-Integer[] data = new Integer[]{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 71, 72};
// root = new BTree<>().delete(root, 20);
// root = new BTree<>().delete(root, 71);
// root = new BTree<>().delete(root, 60);
// root = new BTree<>().delete(root, 80);
// root = new BTree<>().delete(root, 100);
// 随机序列删除测试
Map<String, List<Integer>> testData = generateRandomData(10000);
//System.out.println("insert: " + testData.get("insert"));
//System.out.println("delete: " + testData.get("delete"));
// Integer[] data = new Integer[]{16, 9, 18, 20, 11, 15, 14, 5, 4, 12, 2, 6, 19, 1, 10, 7, 8, 3, 13, 17};
// Integer[] delete = new Integer[]{18, 11, 20, 14, 1, 19, 4, 17, 3, 5, 9, 7, 10, 16, 2, 12, 13, 15, 6, 8};
Integer[] data = testData.get("insert").toArray(new Integer[]{});
// 创建B-树
BTreeNode root = new BTree<Integer>().init(data);
for (int i = 0; i < testData.get("delete").size(); i++){
System.out.println("i=" + i);
root = new BTree<>().delete(root, testData.get("delete").get(i));
}
// for (int i = 0; i < delete.length; i++){
// root = new BTree<>().delete(root, delete[i]);
// }
System.out.println("end");
}
}
结语
通过对B树的理解写的一份Java实现代码，拖了挺久时间。代码只注重了功能实现，优化空间还很大。不能保证代码的完全正确。小数据量的时候是可以验证的。大数据量的测试使用了随机整数序列的插入和删除操作，可以保证最终删除后的树结构是空的，并且不会出现问题，但是不能保证删除过程中的结构是否满足B树的特性，有待验证。
