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;
}
}
代码写的比较丑，还望海涵
分享到：
相关推荐
在Java标准库中并没有内置的B-Tree实现，但很多第三方库如Apache Commons Collections提供了B-Tree的实现。开发者也可以自定义实现，或者利用已有的数据结构如平衡二叉查找树（AVL树、红黑树）作为基础进行改造。 ...
在本项目中，作者根据《算法导论》中的描述实现了B-树的源代码。 首先，`bMinusTree.cpp`文件很可能是B-树的主体实现部分，包含了插入、删除和查找等基本操作的函数。这些操作需要遵循B-树的平衡原则，确保树的高度...
1. **使用KD-TREE快速定位**：先用KD-TREE进行初步的最近邻搜索，得到一批候选点。 2. **构建BBF队列**：将这些候选点加入BBF队列，初始距离为从KD-TREE获取的结果。 3. **BBF搜索**：按照BBF算法进行迭代，每次从...
下面将详细解释FP-Tree算法的核心原理及其在C#中的实现。 **FP-Tree算法概述：** FP-Tree算法由Han等人于2000年提出，主要用于关联规则学习。它的主要目的是通过构建一棵特殊的树结构（FP-Tree）来降低内存消耗和...
在IT领域，数据结构是构建高效算法的基础，而B树（B-Tree）作为一种自平衡的树型数据结构，尤其适用于大量数据的存储系统，如数据库和文件系统。本资源包"BT.rar"包含了Java语言实现B树的相关代码，帮助我们理解和...
在Java中实现k-means聚类算法需要使用到以下几个重要的概念： 1. ArrayList：ArrayList是Java中的一种集合类型，用于存储数据点。 2. Map：Map是Java中的一种集合类型，用于存储质心和簇的对应关系。 3. SQL：SQL是...
基于java的开发源码-最短路径算法实现 k-shortest-paths.zip 基于java的开发源码-最短路径算法实现 k-shortest-paths.zip 基于java的开发源码-最短路径算法实现 k-shortest-paths.zip 基于java的开发源码-最短路径...
通过上述总结可以看出，《算法导论》（第三版）是一本全面介绍了算法理论与实践的教材，涵盖了算法的基础知识、设计技巧、分析方法以及具体的应用实例。适合于计算机科学领域的学生、研究人员以及从业者学习参考。
在Java中实现FP树算法，我们可以按照以下步骤进行： 1. **数据预处理**：首先，我们需要对原始数据进行预处理，将交易数据转换为事务ID和项ID的形式，即每条记录表示一个交易，其中包含交易中出现的所有项。 2. **...
这个压缩包“用Borland C写的B-Tree算法.zip”显然包含了一个使用Borland C编译器实现的B-Tree算法源代码，这为我们提供了学习和理解B-Tree工作原理的一个实用示例。 Borland C++是Borland公司推出的一款早期的C++...
这些文件名揭示了几个经典的计算机科学算法，它们都是在学习《算法导论》时常见的实践练习。下面将分别介绍这些算法及其应用。 1. **矩阵连乘**: 矩阵连乘是线性代数中的一个基本问题，涉及到计算两个或多个矩阵的...
Java 实现 K-Means 算法是一个在数据挖掘领域常见的任务，它主要用于聚类分析，即将数据分组成不同的类别或簇。K-Means 是一种迭代算法，旨在找到数据点的最佳分配，使得每个簇内的数据点尽可能相似，而不同簇之间的...
在IT领域，特别是计算机科学与技术专业中，《算法导论》(Introduction to Algorithms)是一部备受推崇的经典教材，由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein四位作者共同编写。...
decision-tree-js, ID3决策树的小型JavaScript实现 decision-tree-js决策树与随机森林分类器算法的小型JavaScript实现算法。随机森林演示在线演示：http://fiddle.jshell.net/7WsMf/show/light/ 决策树演示在线演示...
算法导论 the introduction to algorithm MIT(两个分卷) 算法导论 the introduction to algorithm MIT(两个分卷) 算法导论 the introduction to algorithm MIT(两个分卷) 算法导论 the introduction to algorithm ...
java 实现FP-Growth算法
算法导论，英文版，附习题解析 Introduction to Algorithms, Second Edition Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein The MIT Press
B-Tree在数据库系统中用于索引管理，例如MySQL的InnoDB存储引擎就使用B-Tree作为索引结构。文件系统如ext4也利用B-Tree来快速定位文件。 **7. B+Tree与B-Tree的区别** B+Tree相对于B-Tree做了优化，所有数据都存储...
- **结构**：KD-Tree是一种二叉树结构，其中每个节点代表一个k维空间中的点，并且树中的每个层次根据不同的维度对点进行分割。 ##### 2.2 构建过程 - **构建原则**：KD-Tree构建过程中，通过递归方式选择合适的...