【アルゴリズム】【アルゴリズム】bツリーの実装(2)---java版コード
17728 ワード
，b RB 。 ， ， 。
package BTree;
public class indexUnit {
public float indexNo;
public Object indexValue=new Object();
}
package BTree;
import java.util.ArrayList;
public class TreeUnit {
public TreeUnit _parent=null;
public ArrayList<indexUnit> keys=new ArrayList<indexUnit>();
public ArrayList<TreeUnit> childNodes=new ArrayList<TreeUnit>();
}
package BTree;
/**
* Created with IntelliJ IDEA.
* User: Administrator
* Date: 13-8-19
* Time: 10:21
* To change this template use File | Settings | File Templates.
*/
public class BtreeGen {
public TreeUnit _btreeRootNode=new TreeUnit();
/*
* ， ，b ，
* b ， +1= 。
* ， ， 1.
* */
public int _m=6;
private int _min=3;
public int totalKeys=1;
/**
* b 。
* */
public BtreeGen(int m){
_m=m;
_min=(int)Math.ceil((double)m/2);
}
public boolean insert(float indexNO,Object indexValue){
indexUnit iunit=new indexUnit();
iunit.indexNo=indexNO;
iunit.indexValue=indexValue;
TreeUnit needInsertLeaf=recursion_insert_search_leaf_node(indexNO, _btreeRootNode);
if(needInsertLeaf==null){
//--
System.out.println("【 】 ！");
return false;
}
else{
System.out.println("【 】 ：");
for(indexUnit iiUnit:needInsertLeaf.keys){
//--
System.out.print(" "+iiUnit.indexNo+" ");
}
}
to_insert(indexNO, indexValue, needInsertLeaf);
return true;
}
private TreeUnit recursion_insert_search_leaf_node(float indexNO,TreeUnit currentUnit){
if(currentUnit==null){
return null;
}
//-- ， 。
if(currentUnit.childNodes.size()>0){
int childLoc=0;
int cindex=0;
for(indexUnit iUnit:currentUnit.keys){
if(iUnit.indexNo<indexNO){
childLoc=cindex+1;
}
if(iUnit.indexNo==indexNO){
//-- ？ ， 。
return null;
}
cindex++;
}
TreeUnit childTree=currentUnit.childNodes.get(childLoc);
return recursion_insert_search_leaf_node(indexNO, childTree);
}
else{
//-- ， 。
return currentUnit;
}
}
/*
* 。
* */
private void to_insert(float indexNO,Object value,TreeUnit currentUnit){
int insertLoc=0;
for(indexUnit iUnit:currentUnit.keys){
if(iUnit.indexNo>indexNO){
break;
}
insertLoc++;
}
indexUnit insertedUnit=new indexUnit();
insertedUnit.indexNo=indexNO;
insertedUnit.indexValue=value;
currentUnit.keys.add(insertLoc, insertedUnit);
if(currentUnit.keys.size()>_m-1){
recursion_division(currentUnit);
}
else{
return;
}
}
private void recursion_division(TreeUnit currentUnit){
if(currentUnit==null){
return;
}
if(currentUnit.keys.size()<=_m-1){
return;
}
if(currentUnit._parent==null){
System.out.println(" 。");
TreeUnit leftTree=new TreeUnit();
TreeUnit rightTree=new TreeUnit();
leftTree._parent=currentUnit;
rightTree._parent=currentUnit;
indexUnit keyUnit=currentUnit.keys.get(_min-1);
int cindex=0;
for (indexUnit tmp:currentUnit.keys) {
if(cindex<_min-1){
leftTree.keys.add(tmp);
}
else if(cindex>=_min){
rightTree.keys.add(tmp);
}
cindex++;
}
int theSize=currentUnit.childNodes.size();
currentUnit.keys.clear();
currentUnit.keys.add(keyUnit);
if(currentUnit.childNodes.size()>0){
//--
for(int ii=0;ii<theSize;ii++){
if(ii<=_min-1){
currentUnit.childNodes.get(ii)._parent=leftTree;
leftTree.childNodes.add(currentUnit.childNodes.get(ii));
}
else{
currentUnit.childNodes.get(ii)._parent=rightTree;
rightTree.childNodes.add(currentUnit.childNodes.get(ii));
}
}
}
currentUnit.childNodes.clear();
currentUnit.childNodes.add(leftTree);
currentUnit.childNodes.add(rightTree);
return;
}
System.out.println(" 。");
//-- 。
indexUnit keyUnit=currentUnit.keys.get(_min-1);
TreeUnit newTreeUnit=new TreeUnit();
newTreeUnit._parent=currentUnit._parent;
int cindex=0;
for (indexUnit tmp:currentUnit.keys) {
if(cindex>=_min){
newTreeUnit.keys.add(tmp);
}
cindex++;
}
int theSize=currentUnit.keys.size();
for(int i2=theSize-1;i2>=_min-1;i2--){
currentUnit.keys.remove(i2);
}
cindex=0;
theSize=currentUnit.childNodes.size();
for(int ii4=theSize-1;ii4>=_min;ii4--){
TreeUnit tmp2=currentUnit.childNodes.get(ii4);
tmp2._parent=newTreeUnit;
if(newTreeUnit.childNodes.size()<=0){
newTreeUnit.childNodes.add(tmp2);
}
else{
newTreeUnit.childNodes.add(0,tmp2);
}
}
for(int ii3=theSize-1;ii3>=_min;ii3--){
currentUnit.childNodes.remove(ii3);
}
int insertPLoc=0;
cindex=0;
for(indexUnit iUnit:currentUnit._parent.keys){
if(iUnit.indexNo<keyUnit.indexNo){
insertPLoc=cindex+1;
}
cindex++;
}
currentUnit._parent.keys.add(insertPLoc, keyUnit);
currentUnit._parent.childNodes.add(insertPLoc+1, newTreeUnit);
//-- 。
if(currentUnit._parent.keys.size()>_m-1){
recursion_division(currentUnit._parent);
}
return;
}
public indexUnit search(float indexNO){
_searchResultUnit=null;
recursion_search(_btreeRootNode,indexNO);
return _searchResultUnit;
}
private indexUnit _searchResultUnit=null;
private void recursion_search(TreeUnit currentUnit, float indexNO){
if(currentUnit==null){
_searchResultUnit=null;
return;
}
for(indexUnit f1:currentUnit.keys){
if(f1.indexNo==indexNO){
_searchResultUnit=f1;
return;
}
}
//-- ， ， 。
if(currentUnit.childNodes.size()<=0){
return;
}
int childTreeIndex=0;
int ccIndex=0;
for(indexUnit f2:currentUnit.keys){
if(f2.indexNo<indexNO){
childTreeIndex=ccIndex+1;
}
ccIndex++;
}
TreeUnit childTreeUnit=currentUnit.childNodes.get(childTreeIndex);
recursion_search(childTreeUnit, indexNO);
}
private TreeUnit _result_treeUnit=null;
/**
* indexNO 。
* */
public TreeUnit getSearchNode(float indexNO){
_result_treeUnit=null;
recursion_search_node(_btreeRootNode, indexNO);
return _result_treeUnit;
}
/**
* indexNO 。
* */
private void recursion_search_node(TreeUnit treeUnit,float indexNO){
if(treeUnit==null){
return;
}
int childChosenIndex=0;
int cindex=0;
for(indexUnit iTMP:treeUnit.keys){
if(indexNO>iTMP.indexNo){
childChosenIndex=cindex+1;
}
if(iTMP.indexNo==indexNO){
_result_treeUnit=treeUnit;
return;
}
cindex++;
}
if(treeUnit.childNodes.size()<=0){
return;
}
//-- ， 。
TreeUnit childTreeUnit=treeUnit.childNodes.get(childChosenIndex);
recursion_search_node(childTreeUnit, indexNO);
}
public int[] getRoute(float indexNO){
return null;
}
public boolean delete(float indexNO){
TreeUnit needDelNode=getSearchNode(indexNO);
if(needDelNode==null){
return false;
}
return deleteNode(needDelNode, indexNO);
}
/**
* 。
* ：
* 1、 ， b ， ：m=6--- 5， 2， ， 》=2， ，
* ：
* 1、 ， ， ，
* 2， ， ， 。
*
* */
public boolean deleteNode(TreeUnit needDelNode,float indexNO){
//System.out.println(" ："+needDelNode.keys.get(0).indexNo);
//-- 。
int indexLoc=-1;
int cindex=0;
for(indexUnit iUnit:needDelNode.keys){
if(iUnit.indexNo==indexNO){
indexLoc=cindex;
}
cindex++;
}
if(indexLoc==-1){
return false;
}
TreeUnit leftChildNode=null;
TreeUnit rightChildNode=null;
if(needDelNode.childNodes.size()>0){
leftChildNode=needDelNode.childNodes.get(indexLoc);
rightChildNode=needDelNode.childNodes.get(indexLoc+1);
}
/**
* ， ， 。
* */
if(needDelNode._parent==null&&(needDelNode.childNodes==null||needDelNode.childNodes.size()<=0)){
needDelNode.keys.remove(indexLoc);
return true;
}
/**
* ， , 。 ， ， ，
* b 。
* */
/**
* a. x ，x->child[i]， x->child[i] n ，
* child[i] max x ， child[i] max。
* ， ， ， keys[i],
* child[i] child[i+1] ---- b 。
* */
if(needDelNode.childNodes!=null&&needDelNode.childNodes.size()>0){
// （ ： 6 b -- 6 ， 3 ， 5 ， 2 ， 3 ）
if(leftChildNode!=null&&leftChildNode.keys.size()>=_min){
int leftLastIndex=leftChildNode.keys.size()-1;
needDelNode.keys.remove(indexLoc);
needDelNode.keys.add(indexLoc,leftChildNode.keys.get(leftLastIndex));
float indexNO1=needDelNode.keys.get(indexLoc).indexNo;
//--
return deleteNode(leftChildNode, indexNO1);
}
//--
else if(rightChildNode.keys.size()>=_min){
int rightLastIndex=0;
needDelNode.keys.remove(indexLoc);
needDelNode.keys.add(indexLoc, rightChildNode.keys.get(0));
return deleteNode(rightChildNode, rightChildNode.keys.get(0).indexNo);
}
else{
//-- ， 。
leftChildNode.keys.add(needDelNode.keys.get(indexLoc));
for(indexUnit iUnit:rightChildNode.keys){
leftChildNode.keys.add(iUnit);
}
for(TreeUnit item1:rightChildNode.childNodes){
leftChildNode.childNodes.add(item1);
}
needDelNode.keys.remove(indexLoc);
needDelNode.childNodes.remove(indexLoc+1);
//-- ， 。
/**
* ： 。
* */
recursion_checkCombination(needDelNode);
return deleteNode(leftChildNode, indexNO);
}
}
/**
*
* ， 。
*
* */
else if(needDelNode.childNodes==null||needDelNode.childNodes.size()<=0){
if(needDelNode.keys.size()>=_min){
needDelNode.keys.remove(indexLoc);
return true;
}
//---
TreeUnit leftBrother=null;
TreeUnit rightBrother=null;
TreeUnit parentNode=needDelNode._parent;
int childIndexLoc=parentNode.childNodes.indexOf(needDelNode);
int keyIndexLoc=-1;
if(childIndexLoc==0){
rightBrother=parentNode.childNodes.get(1);
}
else if(childIndexLoc==parentNode.childNodes.size()-1){
leftBrother=parentNode.childNodes.get(childIndexLoc-1);
}
else{
leftBrother=parentNode.childNodes.get(childIndexLoc-1);
rightBrother=parentNode.childNodes.get(childIndexLoc+1);
}
//-- 。
if(leftBrother!=null&&leftBrother.keys.size()>=_min){
keyIndexLoc=childIndexLoc-1;
needDelNode.keys.add(0,parentNode.keys.get(keyIndexLoc));
parentNode.keys.remove(keyIndexLoc);
parentNode.keys.add(keyIndexLoc,leftBrother.keys.get(leftBrother.keys.size()-1));
leftBrother.keys.remove(leftBrother.keys.size()-1);
return deleteNode(needDelNode, indexNO);
}
// 。
else if(rightBrother!=null&&rightBrother.keys.size()>=_min){
keyIndexLoc=childIndexLoc;
needDelNode.keys.add(parentNode.keys.get(keyIndexLoc));
parentNode.keys.add(keyIndexLoc,rightBrother.keys.get(0));
parentNode.keys.remove(keyIndexLoc+1);
rightBrother.keys.remove(0);///-------------
return deleteNode(needDelNode, indexNO);
}
//-- ， 。
else{
if(leftBrother!=null){
//leftBrother.keys.add(parentNode.keys.get(keyIndexLoc));
keyIndexLoc=childIndexLoc-1;
leftBrother.keys.add(parentNode.keys.get(keyIndexLoc));
for(indexUnit iUnit:needDelNode.keys){
leftBrother.keys.add(iUnit);
}
parentNode.keys.remove(keyIndexLoc);
parentNode.childNodes.remove(keyIndexLoc+1);
recursion_checkCombination(parentNode);
deleteNode(leftBrother, indexNO);
return true;
}
else if(rightBrother!=null){
//needDelNode.keys.remove(indexLoc);
keyIndexLoc=childIndexLoc;
needDelNode.keys.add(parentNode.keys.get(keyIndexLoc));
for(indexUnit iUnit:rightBrother.keys){
needDelNode.keys.add(iUnit);
}
parentNode.keys.remove(keyIndexLoc);
parentNode.childNodes.remove(keyIndexLoc+1);
recursion_checkCombination(parentNode);
deleteNode(needDelNode, indexNO);
return true;
}
else{
return false;
}
}
}
return true;
}
private void recursion_checkCombination(TreeUnit currentUnit){
if(currentUnit==null){
return;
}
if(currentUnit._parent==null&¤tUnit.childNodes.size()<=1){
// ， ， ， 。
_btreeRootNode=currentUnit.childNodes.get(0);
_btreeRootNode._parent=null;
return;
}
// ， ， ， 。
if(currentUnit._parent==null){
return;
}
if(currentUnit.keys.size()>=_min-1){
return;
}
// ， _min-1， 。
/**
* ， ， ， ， ，
* 。
* */
TreeUnit parentNode=currentUnit._parent;
int indexLOC=currentUnit._parent.childNodes.indexOf(currentUnit);
int keyIndexLOC=-1;
int childIndexLOC=indexLOC;
TreeUnit leftBrother=null;
TreeUnit rightBrother=null;
if(parentNode.childNodes.size()==2){
if(childIndexLOC==0){
rightBrother=parentNode.childNodes.get(1);
}
else{
leftBrother=parentNode.childNodes.get(0);
}
}
else if(parentNode.childNodes.size()>=3){
if(childIndexLOC==0){
rightBrother=parentNode.childNodes.get(1);
}
else if(childIndexLOC==parentNode.childNodes.size()-1){
leftBrother=parentNode.childNodes.get(childIndexLOC-1);
}
else{
leftBrother=parentNode.childNodes.get(childIndexLOC-1);
rightBrother=parentNode.childNodes.get(childIndexLOC+1);
}
}
//-- ， 。
if(leftBrother!=null&&leftBrother.keys.size()>=_min){
keyIndexLOC=childIndexLOC-1;
currentUnit.keys.add(0, parentNode.keys.get(keyIndexLOC));
currentUnit.childNodes.add(0,leftBrother.childNodes.get(leftBrother.childNodes.size()-1));
parentNode.keys.remove(keyIndexLOC);
parentNode.keys.add(keyIndexLOC,leftBrother.keys.get(leftBrother.keys.size()-1));
leftBrother.keys.remove(leftBrother.keys.size()-1);
leftBrother.childNodes.remove(leftBrother.childNodes.size()-1);
return;
}
//-- ，
else if(rightBrother!=null&&rightBrother.keys.size()>=_min){
keyIndexLOC=childIndexLOC;
currentUnit.keys.add(parentNode.keys.get(keyIndexLOC));
currentUnit.childNodes.add(rightBrother.childNodes.get(0));
parentNode.keys.remove(keyIndexLOC);
parentNode.keys.add(rightBrother.keys.get(0));
rightBrother.keys.remove(0);
rightBrother.childNodes.remove(0);
return;
}
//-- ， 。
else{
//--
if(leftBrother!=null){
keyIndexLOC=childIndexLOC-1;
leftBrother.keys.add(parentNode.keys.get(keyIndexLOC));
for(indexUnit iUnit:currentUnit.keys){
leftBrother.keys.add(iUnit);
}
for(TreeUnit tUnit:currentUnit.childNodes){
leftBrother.childNodes.add(tUnit);
tUnit._parent=leftBrother;
}
parentNode.keys.remove(keyIndexLOC);
parentNode.childNodes.remove(keyIndexLOC+1);
recursion_checkCombination(parentNode);
return;
}
else{
//--
keyIndexLOC=childIndexLOC;
currentUnit.keys.add(parentNode.keys.get(keyIndexLOC));
for(indexUnit iUnit:rightBrother.keys){
currentUnit.keys.add(iUnit);
}
for(TreeUnit iUnit:rightBrother.childNodes){
currentUnit.childNodes.add(iUnit);
iUnit._parent=currentUnit;
}
parentNode.keys.remove(keyIndexLOC);
parentNode.childNodes.remove(keyIndexLOC+1);
recursion_checkCombination(parentNode);
return;
}
}
}
}