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;
}
}
代码写的比较丑，还望海涵
分享到：
相关推荐
本文将深入探讨如何使用Python来实现FP-TREE算法，并通过Python3.2进行演示。为了可视化FP树的生成过程，需要安装PIL库来处理图像。 首先，我们需要理解关联规则挖掘的基本概念。关联规则通常由两部分组成：前提...
实现基于R-Tree的DBSCAN算法，开发者可以利用Java的库，如JTS（Java Topology Suite）或GeoTools，它们提供了R-Tree的实现，并且与地理空间数据操作兼容。 在"DBSCAN_06"这个文件中，可能包含了以下内容： 1. R-...
下面将详细解释FP-Tree算法的核心原理及其在C#中的实现。 **FP-Tree算法概述：** FP-Tree算法由Han等人于2000年提出，主要用于关联规则学习。它的主要目的是通过构建一棵特殊的树结构（FP-Tree）来降低内存消耗和...
在Java中实现k-means聚类算法需要使用到以下几个重要的概念： 1. ArrayList：ArrayList是Java中的一种集合类型，用于存储数据点。 2. Map：Map是Java中的一种集合类型，用于存储质心和簇的对应关系。 3. SQL：SQL是...
在这个主题下，我们将探讨如何将书中的算法用Java语言进行实现，以及如何通过源码和工具来理解和学习这些算法。 在Java中实现《算法导论》中的算法，首先需要理解算法的基本思想和逻辑结构。这包括排序算法（如冒泡...
通过上述总结可以看出，《算法导论》（第三版）是一本全面介绍了算法理论与实践的教材，涵盖了算法的基础知识、设计技巧、分析方法以及具体的应用实例。适合于计算机科学领域的学生、研究人员以及从业者学习参考。
这个压缩包“用Borland C写的B-Tree算法.zip”显然包含了一个使用Borland C编译器实现的B-Tree算法源代码，这为我们提供了学习和理解B-Tree工作原理的一个实用示例。 Borland C++是Borland公司推出的一款早期的C++...
### FP-Tree算法详解及其Java源码实现 在数据挖掘领域，尤其是关联规则挖掘中，寻找频繁模式是一项核心任务。传统的Apriori算法虽然有效，但因需多次扫描数据库而存在效率瓶颈。针对这一问题，韩嘉炜教授提出的FP-...
这些文件名揭示了几个经典的计算机科学算法，它们都是在学习《算法导论》时常见的实践练习。下面将分别介绍这些算法及其应用。 1. **矩阵连乘**: 矩阵连乘是线性代数中的一个基本问题，涉及到计算两个或多个矩阵的...
这个C++实现版本提供了FP-TREE算法的完整功能，包括构建FP树、查找频繁项集以及进行关联规则挖掘。 在数据挖掘中，频繁项集是指在数据集中出现次数超过预设阈值的项集合。FP-TREE算法通过构建一棵特殊的树结构来...
在IT领域，特别是计算机科学与技术专业中，《算法导论》(Introduction to Algorithms)是一部备受推崇的经典教材，由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein四位作者共同编写。...
算法导论 the introduction to algorithm MIT(两个分卷) 算法导论 the introduction to algorithm MIT(两个分卷) 算法导论 the introduction to algorithm MIT(两个分卷) 算法导论 the introduction to algorithm ...
《算法导论》是计算机科学领域的一本经典著作，它深入浅出地介绍了算法的设计、分析和实现。这本书广泛应用于大学计算机科学课程中，对于学习和理解算法有着极高的价值。在Java编程环境下，我们可以利用Java语言来...
算法导论习题答案13.3-1，需要安装OpenOffice 打开。
《算法导论》是计算机科学领域的一本经典著作，它深入浅出地介绍了算法的设计、分析和实现。这本书涵盖了从基础的数据结构到高级的算法分析，对于学习和理解算法有着极高的价值。习题是书中的重要组成部分，它们旨在...
中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部
算法导论第15章-动态规划的课后习题参考答案，对于算法爱好者而言，是不错的参考资料。
simhash 算法的 java 实现。特点计算字符串的 simhash通过构建智能索引来计算所有字符串之间的相似性，因此可以处理大数据使用使用输入文件和输出文件运行 Maininputfile 的格式（参见 src / test_in）：一个文件每...