B-tree(多路搜索树),数据结构的一种，使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。
算法导论18章介绍的B-TREE 特性：
1、每个叶结点具有相同的深度。
2、假如树的度为T(子节点数),则根节点的关键字最少1个，最多2t-1个，非根节点，最少
t-1个，最多2t-1个。
3、根最少2个子节点，最多2t个子节点，非根非叶子节点，至少t个子节点，最多2t个子女。
添加和删除思路：
添加：
当向一个节点添加关键字的时候，如果此节点关键字已饱和，则需要分裂，并且此分裂会向上层传递，因为上层可能也饱和，分裂到上层的关键字需要在上层分裂之后再插入。
所以，可以考虑，插入节点的时候，从根部到目的节点，沿途遇到饱和的节点就进行分裂。可以避免回溯。
删除：
从根到目的节点沿途节点，遇到不大于t-1的节点时，则从兄弟节点弄关键字名额（经过父节点转换），如果兄弟节点也是不大于t-1,则进行合并。
把要删除的关键字沉降到叶子节点，和叶子节点上大于目标关键字的最小关键字进行位置交换，将目标关键字转移到叶子节点进行删除，然后还需要对此叶子节点进行调整以符合B-TREE特性。
package com.btree;
import java.util.LinkedList;
import java.util.List;
/**
*每个叶结点具有相同的深度。树的高度h 树的度为t
*每个结点的关键字 非根至少t-1个，至多2t-1 个,根至少1个
*非根非叶子结点最少t子女，最多2t个子女
*根至少2两个子女,最多2t个子女
*@author yuyong 2012-12-6
*@wuhu ruixin
*/
public class BTree {
public static Integer M=3;
private BTreeNode root;
public static void main(String args[]){
BTree tree=new BTree();
String str="";
// int[] keys=new int[]{71,10, 14, 31, 54,3, 4, 5,11, 12,15, 23, 25, 27,32, 35, 40, 43, 48,55, 57, 63, 67, 68,
// 78, 88,72, 73,81, 86, 87,91, 92, 94, 95};
// for(int index=0;index<keys.length;index++){
// int key=keys[index];
// str+=key+" ";
// tree.add(key);
// }
int[] keys=new int[3];
int j=0;
for(int i=1;i<=10000;i++){
int key=(int) (Math.random()*100);
if(i==10||i==24||i==30){
keys[j]=key;
j++;
}
tree.add(key);
}
tree.printTree();
for(int key:keys){
tree.delete(key);
System.out.println(key);
tree.printTree();
}
}
public void printTree(){
String keys="";
keys+=this.printNode(root);
System.out.println(keys);
}
public String printNode(BTreeNode node){
String str=" \n结点:位置 "+node.position+" ";
str+=node.keys.toString();
if(node.sons.size()>0){
for(BTreeNode n:node.sons){
str+=printNode(n);
}
}
return str;
}
public void add(int key){
if(root==null){
root=new BTreeNode(key);
root.position=0;
return;
}
this.add(root, key);
}
public void add(BTreeNode node,int key){
if(node.keys.indexOf(key)!=-1)
return;
if(node.keys.size()>=(2*BTree.M-1))
node=split(node);
int index=binarySearch(node,key);
if(node.sons.size()>0){
if(node.sons.get(index)!=null){
add(node.sons.get(index),key);
}else
node.keys.add(index, key);
}else{
node.keys.add(index, key);
}
}
public void delete(int key){
if(root==null)
return;
this.delete(root, key);
}
//删除节点
public void delete(BTreeNode node,int key){
int index=node.keys.indexOf(key);
if(index==-1){
if(node.sons.size()>0){
index=binarySearch(node,key);
if(node.father!=null||node.keys.size()<(BTree.M-1)){
node=configKeys(node);
index=binarySearch(node,key);
}
delete(node.sons.get(index),key);
}
}else{
deleteAndCombine(node,index);
}
}
//分裂已经满关键字的节点。当向节点添加关键字的时候，如果此节点已经满关键字，则进行分裂。并且沿途分裂已经满的关键字（即使关键字不需要插入到此节点中)
public BTreeNode split(BTreeNode node){
if(node.keys.size()<(2*BTree.M-1))
return node;
int n1=BTree.M-1-1;
int n2=n1+1;
int n3=2*BTree.M-1-1;
BTreeNode nodeFather=node.father;
LinkedList<Integer> newNodesKeys=new LinkedList<Integer>();
newNodesKeys.addAll(node.keys.subList(n2+1, n3+1));
BTreeNode newNode=new BTreeNode(newNodesKeys);
newNode.position=node.position+1;
List<Integer>lists=new LinkedList<Integer>();
lists.addAll(node.keys.subList(0, n1+1));
if(nodeFather==null){
nodeFather=new BTreeNode();
nodeFather.keys.add(node.keys.get(n2));
nodeFather.sons.add(0,node);
newNode.father=nodeFather;
nodeFather.sons.add(1,newNode);
nodeFather.position=0;
node.father=nodeFather;
root=nodeFather;
}else{
nodeFather.keys.add(node.position, node.keys.get(n2));
newNode.father=nodeFather;
nodeFather.sons.add(node.position+1,newNode);
for(int i=node.position+2;i<=nodeFather.sons.size()-1;i++){
nodeFather.sons.get(i).position=i;
}
}
if(node.sons.size()>0){
LinkedList<BTreeNode> newSons=new LinkedList<BTreeNode>();
LinkedList<BTreeNode> sons=new LinkedList<BTreeNode>();
newSons.addAll(node.sons.subList(BTree.M, 2*BTree.M));
for(int i=0;i<=newSons.size()-1;i++){
newSons.get(i).position=i;
newSons.get(i).father=newNode;
}
sons.addAll(node.sons.subList(0, BTree.M));
newNode.sons=newSons;
node.sons.clear();
node.sons.addAll(sons);
}
node.keys.clear();
node.keys.addAll(lists);
return split(nodeFather);
}
//合并两个节点
public void combine(BTreeNode node1,BTreeNode node2){
BTreeNode f=node1.father;
if(f.sons.size()==2){
node1.keys.addAll(f.keys);
node1.keys.addAll(node2.keys);
f.sons.remove(1);
node1.father=null;
root=node1;
}else{
node1.keys.add(f.keys.get(node1.position));
node1.keys.addAll(node2.keys);
f.keys.remove(node1.position);
f.sons.remove(node2.position);
}
for(int i=node2.position;i<f.sons.size();i++)
f.sons.get(i).position=i;
for(int i=0,j=node1.sons.size();i<node2.sons.size();i++,j++){
node2.sons.get(i).position=j;
node2.sons.get(i).father=node1;
}
node1.sons.addAll(node2.sons);
configKeys(f);
}
//删除关键字，searchLeft搜到比要删除关键字大的最小关键字所在叶子节点，将此关键字和其对换，沉底到叶子节点进行删除，然后还要对叶子节点进行
//一些符合B-tree的调整
public void deleteAndCombine(BTreeNode node,int keyIndex) {
if(node.sons.size()>0){
BTreeNode left=searchLeft(node.sons.get(keyIndex+1));
node.keys.remove(keyIndex);
node.keys.add(keyIndex,left.keys.get(0));
left.keys.remove(0);
configKeys(left);
}else{
node.keys.remove(keyIndex);
configKeys(node);
}
}
//搜索node子节点中最左结点
public BTreeNode searchLeft(BTreeNode node){
if(node.sons.size()>0){
return searchLeft(node.sons.get(0));
}else{
return node;
}
}
/**
* 避免回溯，从树根向下搜索关键字的过程中，凡是遇到途经的结点，如果该结点的关键字数是t-1，
* 想办法从其他地方弄关键字过来，使得该结点的关键字数至少为t。
* 考虑从相邻结点弄，如果相邻结点有的话，经过父结点进行周转。如果没有，
* 就说明相邻结点的关键字个数也是t-1，这种情况，直接对该结点与其相邻结点进行合并，以满足要求。
* @param node
*/
public BTreeNode configKeys(BTreeNode node){
if(node.keys.size()<=BTree.M-1){
BTreeNode f=node.father;
BTreeNode nodeRight=null;
BTreeNode nodeLeft=null;
if(f==null)
return node;
if(node.position==0)
nodeRight=f.sons.get(node.position+1);
else if(node.position==f.keys.size())
nodeLeft=f.sons.get(node.position-1);
else{
nodeLeft=f.sons.get(node.position-1);
nodeRight=f.sons.get(node.position+1);
}
if(nodeRight!=null&&nodeRight.keys.size()>BTree.M-1){
int temp=f.keys.get(node.position);
f.keys.remove(node.position);
f.keys.add(node.position, nodeRight.keys.get(0));
nodeRight.keys.remove(0);
node.keys.add(temp);
if(nodeRight.sons.size()>0){
BTreeNode n=nodeRight.sons.get(0);
n.position=node.sons.size();
n.father=node;
node.sons.add(n);
nodeRight.sons.remove(0);
for(int i=0;i<nodeRight.sons.size();i++)
nodeRight.sons.get(i).position=i;
}
return node;
}else if(nodeLeft!=null&&nodeLeft.keys.size()>BTree.M-1){
int temp=f.keys.get(node.position-1);
f.keys.remove(node.position-1);
f.keys.add(node.position-1, nodeLeft.keys.get(nodeLeft.keys.size()-1));
nodeLeft.keys.remove(nodeLeft.keys.size()-1);
node.keys.add(0,temp);
if(nodeLeft.sons.size()>0){
BTreeNode n=nodeLeft.sons.get(nodeLeft.sons.size()-1);
n.position=0;
n.father=node;
node.sons.add(0,n);
for(int i=1;i<node.sons.size();i++)
node.sons.get(i).position=i;
nodeLeft.sons.remove(nodeLeft.sons.size()-1);
}
return node;
}else{
if(nodeLeft!=null){
combine(nodeLeft,node);
return nodeLeft;
}else if(nodeRight!=null){
combine(node,nodeRight);
return node;
}
}
}
return node;
}
//二分查找
public int binarySearch(BTreeNode node,Integer key){
int index=0;
if(node.keys.size()>0){
int start=0;
int end=node.keys.size()-1;
int step=0;
if(start!=end)
while((end-start)!=1){
step=(end-start)/2;
if(node.keys.get(start+step)>key){
end=end-step;
}else if(node.keys.get(start+step)<key){
start=start+step;
}else{
return start+step;
}
}
if(key>=node.keys.get(end)){
index=end+1;
}else if(key<=node.keys.get(start)){
index=start;
}else
index=end;
}
return index;
}
}
package com.btree;
import java.util.LinkedList;
/**
*
* @author yuyong 2012-12-6
* @wuhu ruixin
*/
public class BTreeNode {
public BTreeNode father;
public LinkedList<BTreeNode> sons=new LinkedList<BTreeNode>();
public LinkedList<Integer> keys=new LinkedList<Integer>();
public boolean leaf;
public int position;
public BTreeNode(){}
public BTreeNode(int key){
keys.add(key);
}
public BTreeNode(LinkedList<Integer> keys){
this.keys=keys;
}
}
代码写的比较丑，还望海涵
分享到：
相关推荐
python3.2实现FP-TREE挖掘算法,可以显示每一步FP树的图片
[麻省理工学院-算法导论[麻省理工学院-算法导论[麻省理工学院-算法导论[麻省理工学院-算法导论[麻省理工学院-算法导论[麻省理工学院-算法导论[麻省理工学院-算法导论[麻省理工学院-算法导论[麻省理工学院-算法导论...
详解python实现FP-TREE进行关联规则挖掘 python3.2实现,可以生成每一步fp树的图片(需要安装PIL)
进程调度的两种算法JAVA实现----FCFS(先来先服务)和SJF(最短作业优先) 直接能运行，完整版本，jdk 1.6就行
上学时 一些算法导论的代码----矩阵连乘，弗洛伊德，bellman 01背包 n皇后
自己写的b-树模板,已通过800万个数据测试,用的结构是算法导论上的,严渭敏树上的3叉树是2-3树,做删除操作比较麻烦,而算法导论上的是2-3-4树,可以方便实现删除.
柯尔曼-算法导论-第2版-习题解答 柯尔曼-算法导论-第2版-习题解答 柯尔曼-算法导论-第2版-习题解答 柯尔曼-算法导论-第2版-习题解答
对DBSCAN算法的改进，使用R-Tree算法对DBSCAN的改进
MIT算法导论-Introduction to Algorithms-算法实现
生物信息学算法导论，英文原版 an-introduction-to-bioinformatics-algorithms，有需要的可以下载
MIT课程算法导论6-046JFall-2005
K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-...
Java 算法导论 电子书Java 算法导论 电子书Java 算法导论 电子书
基于java的开发源码-最短路径算法实现 k-shortest-paths.zip 基于java的开发源码-最短路径算法实现 k-shortest-paths.zip 基于java的开发源码-最短路径算法实现 k-shortest-paths.zip 基于java的开发源码-最短路径...
算法导论----算法经典书籍----不用我多做介绍了吧。算法导论----算法经典书籍----不用我多做介绍了吧。
算法导论：概述基本算法！对一个编程人员来说，算法很重要，一个好的算法，可以让你的软件运行效果好
算法导论 the introduction to algorithm MIT(两个分卷) 算法导论 the introduction to algorithm MIT(两个分卷) 算法导论 the introduction to algorithm MIT(两个分卷) 算法导论 the introduction to algorithm ...
最快的排序算法 javahash实现-Java-哈希算法-最快的实现，排序算法数据结构
java语言实现对mysql数据库表中某个字段实现k-means算法，并将处理后的数据写入新表
decision-tree-js, ID3决策树的小型JavaScript实现 decision-tree-js决策树与随机森林分类器算法的小型JavaScript实现算法。随机森林演示在线演示：http://fiddle.jshell.net/7WsMf/show/light/ 决策树演示在线演示...