1 package edu.algorithms.btree; import java.util.ArrayList;
import java.util.List; /**
* BTree类
*
* @author lingfeng
*
*/
public class BTree { /**BTree 基础参数信息配置
最小度数 t=2时，称作2-3-4数，表示只能存在2、3、4子女数**/
private int t = 2; /**非根节点最小关键字数**/
private int minKeys = t-1; /**内节点最大关键字数**/
private int maxKeys = 2*t - 1; /**树根节点**/
private BTreeNode root; /**构造函数**/
public BTree(){
//初始化
root = new BTreeNode();
root.setLeaf(true);
}
/**构造函数 t 最小度数**/
public BTree(int t){
this();
this.t = t;
minKeys = t - 1;
maxKeys = 2*t - 1;
} /**插入元素
*
* 1.元素存在，插入元素
* 2.元素不存在，插入元素
*
* **/
public void insertNode(Integer key){
if(root.size() == maxKeys){ //根节点已满
//进行根节点分割
BTreeNode tmpNode = new BTreeNode();
tmpNode.setLeaf(false);
tmpNode.getChildrens().add(root);
btreeSplitChild(tmpNode, 0, root);
root = tmpNode;
}
insertRootNotFull(root, key);
} public void insertRootNotFull(BTreeNode node, int key){ //如果该节点为叶子节点
if(node.isLeaf()){
//寻找当前节点所有关键字
ResultSearch result = divideSearch(node.getKeys(), key);
//查询结果：成功 返回已经存在关键字位置
if(result.result == true){ }else{ //查询结果：失败 返回插入位置
node.insertKey(key, result.index);
} }else{
//寻找当前节点所有关键字
ResultSearch result = divideSearch(node.getKeys(), key);
//查询结果：成功 返回已经存在关键字位置
if(result.result == true){ }else{ //查询结果：失败 返回插入子女节点的位置
//判断子女状态
BTreeNode childNode = node.childAt(result.index);
if(node.childAt(result.index).size() == (2*t - 1)){
btreeSplitChild(node, result.index, childNode);
if(key > node.keyAt(result.index)){ //判断key落在 前半部分 或 后半部分
childNode = node.childAt(result.index + 1);
}
}
insertRootNotFull(childNode, key);
}
}
}
/**查询元素 (BTree查询)
*
* 1.先查询节点的关键字列表
* 2.失败则，查询子女节点；成功则，返回值
* 3.递归搜索
*
* **/
public Integer search(BTreeNode node,Integer key){
List<Integer> keys_tmp = node.getKeys();
ResultSearch result = divideSearch(keys_tmp, key);
if(result.result){
return result.index;
}else{
return search(node.childAt(result.index), key);
}
}
/**二分查询
* 参数 元素列表、所需要查询元素的值
*
* **/
public ResultSearch divideSearch(List<Integer> elements, int key){ int start = 0; //扫描起始位置
int end = 0; //扫描结束位置 end = elements.size() - 1; int mid = 0;
while(start<=end){
mid = (start + end)/2;
if(elements.get(mid) == key){ //满足等值条件
break;
}else if(elements.get(mid) > key){ //在列表前半部分
//改变扫描结束位置
end = mid - 1;
}else if(elements.get(mid) <= key){
//改变扫描开始位置
start = mid + 1;
}
} boolean result = false;
Integer index = 0; if(start<=end){ //二分查找成功
result = true;
index = mid;
}else{ //查找失败，不存在元素
result = false;
index = start;
} return new ResultSearch(result,index);
} /**
* 节点分割函数
* @param parentNode 被分割节点的父节点
* @param index 被分割节点在父节点的第index个子女索引位置
* @param Node 被分割节点
*/
public void btreeSplitChild(BTreeNode parentNode, int index, BTreeNode node){ //新建一个节点，保存分割后[t+1 2t-1]数据
BTreeNode subNode = new BTreeNode();
//必须加上
subNode.setLeaf(node.isLeaf()); for(int i=1; i<=minKeys ; i++){
subNode.getKeys().add(node.keyAt(t + i -1));
}
//保存分割点值[t]
Integer key = node.keyAt(t - 1);
//删除被分割节点的[t 2t-1]数据
for(int i= maxKeys - 1; i>=minKeys; --i){
node.getKeys().remove(i);
}
if(!node.isLeaf()){ //如果满节点不是叶节点，关键字分割后，需要将其子女进行操作 //subNode应该拥有后半部分的子女
for(int i=0 ; i<minKeys+1 ; ++i){
subNode.getChildrens().add(node.childAt(i+t));
}
//并删除node后半部分的子女
for(int i=maxKeys ; i>=minKeys+1; --i){
node.getChildrens().remove(i);
}
}else{ }
//将[t]数据加入父节点中去
parentNode.insertKey(key, index);
//将新节点关联到父节点index+1子女中
parentNode.insertChild(subNode, index+1);
}
public void delete(Integer key){
delete(root, key);
} 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);
}
} }
} }
class BTreeNode{ /**当前节点keys列表**/
private List<Integer> keys; /**当前节点的child列表**/
private List<BTreeNode> childrens; /**是否是叶子节点**/
private boolean leaf; public BTreeNode(){
keys = new ArrayList<Integer>();
childrens = new ArrayList<BTreeNode>();
leaf = true;
}
/**
* set and get methods
*
* **/
public List<Integer> getKeys() {
return keys;
}
public void setKeys(List<Integer> keys) {
this.keys = keys;
}
public List<BTreeNode> getChildrens() {
return childrens;
}
public void setChildrens(List<BTreeNode> childrens) {
this.childrens = childrens;
}
public boolean isLeaf() {
return leaf;
}
public void setLeaf(boolean leaf) {
this.leaf = leaf;
} /**
* 获取子女节点
* @param index
* @return
*/
public BTreeNode childAt(int index){
return childrens.get(index);
}
/**
* 获取关键字
* @param index
* @return
*/
public Integer keyAt(int index){
return keys.get(index);
} /**
* 获取节点关键字数量
* @return
*/
public int size(){
return keys.size();
} /**
* 插入key到指定的index中去
* @param key
* @param index
*/
public void insertKey(Integer key, int index){
//插入key到指定的索引位置
//保存索引前的所有关键字
List<Integer> newlist = new ArrayList<Integer>(); for(int i=0; i<index ; i++){
newlist.add(keys.get(i));
}
//插入关键字
newlist.add(key);
//保存索引后多关键字
for(int i=index ; i<keys.size() ; i++){
newlist.add(keys.get(i));
}
//将新的关键字集合设置为节点关键字集合对象
keys = newlist;
} /**
* 插入node子女到指定的index位置
* @param node
* @param index
*/
public void insertChild(BTreeNode node, int index){
//插入child
List<BTreeNode> newlist = new ArrayList<BTreeNode>();
for(int i=0 ; i< index ; i++){
newlist.add(childrens.get(i));
}
newlist.add(node);
for(int i=index ; i<childrens.size() ; i++){
newlist.add(childrens.get(i));
}
childrens = newlist;
}
}
/**
* 查询结果类
* result 标识成功的状态 true or false
* index 成功后返回元素的索引
* 失败后返回元素的插入位置
* @author lingfeng
*/
class ResultSearch{ public Integer index;
public boolean result; public ResultSearch(boolean rs, Integer i){
index = i;
result = rs;
}
}