编程内功修炼之数据结构—BTree(三)总结

时间:2023-03-09 07:42:40
编程内功修炼之数据结构—BTree(三)总结

BTree必须通过各种编程约束,使得不脱离BTree的本身特性;

1)BTree关键字插入操作;插入过程中,如果节点关键字达到上限,添加分裂约束,从而控制每个节点的关键字数维持在 t-1~2*t-1内;

2)BTree节点中的关键字查询;因为关键字按非降序进行排列,所以可以采用二分查找方法进行查询,以提高算法性能;

3)BTree关键字删除操作;

 删除操作必须保证节点关键字数n[x]>=t,这样删除一个关键字才不会违反BTree规则。

当前节点是叶节点,可以直接删除;

当前节点是内节点,可以寻找左右子女节点进行关键字替代;

当前节点不足t方案:

    (a)如果当前节点关键字不足t,可以向兄弟节点进行借取;

  (b)如果左右相近兄弟节点都不满足>=t要求,那么可以采用合并方式;

Delete实现方法如下:

 public void delete(BTreeNode node, Integer key){
//删除关键字时,必须保证关键字大于等于t
assert node.size() >=t || node == root; //对当前节点进行二分查找
ResultSearch resultSearch = divideSearch(node.getKeys(), key); //成功
if(resultSearch.result){ //如果当前节点属于叶子节点,可以直接进行删除
if(node.isLeaf()){
node.getKeys().remove(resultSearch.index.intValue());
}else{
//如果不是叶子节点 ,判断前于key子节点状态
BTreeNode leftChildNode = node.childAt(resultSearch.index);
if(leftChildNode.size() >= t){ //从leftChildNode进行借值 代替当前需要删除的关键字
//删除当前节点关键字
node.getKeys().remove(resultSearch.index.intValue());
node.insertKey(leftChildNode.keyAt(leftChildNode.size()-1), resultSearch.index);
delete(leftChildNode, leftChildNode.keyAt(leftChildNode.size()-1));
}else{ BTreeNode rightChildNode = node.childAt(resultSearch.index + 1);
if(rightChildNode.size() >= t){ //从rightChildNode进行借值 代替当前需要删除的关键字
node.getKeys().remove(resultSearch.index.intValue());
node.insertKey(rightChildNode.keyAt(0), resultSearch.index);
delete(rightChildNode, rightChildNode.keyAt(0));
}else{ //对于索引的左右子节点的数量都等于t-1
//合适进行合并
//1.将父节点删除 将节点右子节点删除
node.getKeys().remove(resultSearch.index.intValue());
node.getChildrens().remove(resultSearch.index.intValue() + 1);
//2.将父节点添加到左子节点上
leftChildNode.getKeys().add(key);
//3.将删除的右子节点添加到左子节点上
for(int i=0 ; i<rightChildNode.size() ; i++){
leftChildNode.getKeys().add(rightChildNode.getKeys().get(i));
}
//如果右子节点非叶子节点,需要将其子女继承到左节点之下
if(!rightChildNode.isLeaf()){
for(int k=0 ; k<=rightChildNode.size() ; k++){
leftChildNode.getChildrens().add(rightChildNode.childAt(k));
}
}
//递归删除
delete(leftChildNode, key); }
} } }else{ //失败
if(node.isLeaf()){
//不存在删除的对象
System.out.println("不存在删除的对象");
return ;
} //获取子节点
BTreeNode childNode = node.childAt(resultSearch.index); if(root == node && node.size()==0){
root = childNode;
} if(childNode.size() >= t){ //如果满足递归条件
delete(childNode, key);
}else{
//不满足size == t
//采取借关键字手段 BTreeNode subNode = null;
int subIndex = 0;
//先检测右兄弟节点
if(resultSearch.index < node.size()){
if(node.childAt(resultSearch.index+1).size() >=t){
subNode = node.childAt(resultSearch.index+1);
subIndex = resultSearch.index + 1;
}
}
//测试左兄弟节点
if(subNode == null){
if(resultSearch.index > 0){
if(node.childAt(resultSearch.index-1).size() >= t){
subNode = node.childAt(resultSearch.index-1);
subIndex = resultSearch.index - 1;
}
}
}
//测试完成后
if(subNode != null){ //存在兄弟节点大于等于t情况
//判断节点
if(subIndex > resultSearch.index){ //右兄弟 //将右关键字插入自身
childNode.insertKey(node.keyAt(subIndex - 1), childNode.size());
node.getKeys().remove(subIndex - 1);
node.insertKey(subNode.keyAt(0), subIndex - 1);
subNode.getKeys().remove(0); //右兄弟非子叶节点,则带有孩子节点
if(!subNode.isLeaf()){
childNode.getChildrens().add(subNode.getChildrens().get(0));
subNode.getChildrens().remove(0);
} }else{ //左兄弟 //将左关键字插入自身最前位置
childNode.insertKey(node.keyAt(subIndex), 0);
node.getKeys().remove(subIndex);
node.insertKey(subNode.keyAt(subNode.size()-1), subIndex);
subNode.getKeys().remove(subNode.size()-1); //如果左兄弟非子叶节点
if(!subNode.isLeaf()){
childNode.insertChild(subNode.childAt(subNode.size()), 0);
subNode.getChildrens().remove(subNode.size()-1);
}
}
delete(childNode, key); }else{ //该节点的左右兄弟节点关键字都为t-1
//选择合并方案
if(resultSearch.index < node.size()){ //右兄弟存在 subNode = node.childAt(resultSearch.index + 1); //childNode.getKeys().add(node.keyAt(resultSearch.index + 1));
childNode.getKeys().add(node.keyAt(resultSearch.index)); node.getKeys().remove(resultSearch.index.intValue());
node.getChildrens().remove(resultSearch.index.intValue()); for(int i=0 ; i<subNode.size() ; i++){
childNode.getKeys().add(subNode.keyAt(i));
} if(!subNode.isLeaf()){
for(int k=0 ; k<=subNode.size(); k++){
childNode.getChildrens().add(subNode.childAt(k));
}
} }else{ //左兄弟存在 subNode = node.childAt(resultSearch.index - 1);
childNode.insertKey(node.keyAt(resultSearch.index-1), 0);
node.getKeys().remove(resultSearch.index - 1);
node.getChildrens().remove(resultSearch.index-1); for(int i=subNode.size()-1 ; i>=0 ; --i){
childNode.insertKey(subNode.keyAt(i), 0);
} if(!subNode.isLeaf()){
for(int k=subNode.size() ; k>=0 ; --k){
childNode.insertChild(subNode.childAt(k),0);
}
} }
if(root == node && node.size() == 0){
root = childNode;
}
delete(childNode, key);
}
} }
}