根据算法导论用java实现的b-tree

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;
	}
}

代码写的比较丑，还望海涵

评论

1 楼 shliujing 2016-08-09  

good!!!