B树的查找和插入-白红宇

B树的查找和插入

阅读量：323 次

发布时间：2019-03-04

本文共 2683 字，大约阅读时间需要 8 分钟。

找了一本书《数据结构教程(Java语言描述)，徐孝凯主编》，写的挺好的，我发上来大家一起学习。

package p215;public class BayerTreeNode {   	/*根节点非叶节点至少两个分支，非根非叶至少m/2上整个分支	最多m个分支	每个节点关键字的个数是比分支数少一	如非根非叶关键字个数(m/2取上整-1)——(m-1)	*/	int m;//B-tree的阶，即节点中可容纳孩子节点个数(子树)的最大值	      //(m>=3)	int keyNum;//实际存储了几个节点	BayerTreeNode parent;//指向父节点的指针域	Object []key=new Object[m+1];//，保存关键字的域	BayerTreeNode[]ptr=new BayerTreeNode[m+1];//指向子树的指针域	int[]rec=new int[m+1];//保存关键字对应记录的位置	//key、rec从1开始,ptr从0开始}

书中为了查找和插入方便，在每个节点的所有关键字后面放上MaxKey，这个最大的键不计入keynum

查找

package p215;public class BayerTree {   	private int m;//m-阶B树	private BayerTreeNode bt;//根	final int MaxKey=1000;//最大键值		//注意原来的书里面添加最后一个位置为最大的MaxKey	//查找时一定会小于最后的位置，不会超过	   		public int search(Object k)	{   		int i;		BayerTreeNode p=bt;		while(p!=null)		{   			i=1;			while(((Comparable)k).compareTo(p.key[i])>0)					i++;			if(k.equals(p.key[i]))				return p.rec[i];			else p=p.ptr[i-1];		}		return -1;	}

插入

public boolean insert(Object k,int num)	{   		//向B树中插入关键字为k,记录存储位置为num的记录						//当树为空		if(bt==null)		{   			bt=new BayerTreeNode();			bt.keyNum=1;bt.parent=null;			bt.key[1]=k;bt.key[2]=MaxKey;			bt.rec[1]=num;			bt.ptr[0]=bt.ptr[1]=null;			return true;		}						//从树上查找插入位置		int i=0;		BayerTreeNode xp=bt,p=null;//分别指向当前节点和父节点		while(xp!=null)		{   			i=1;			while(((Comparable)k).compareTo(xp.key[i])>0)					i++;			if(k.equals(p.key[i]))				return false;			else {   				p=xp;				xp=xp.ptr[i-1];			}		}		BayerTreeNode ap=null;				//向非空的B树中p节点的第i个位置插入索引项(k,num,ap)		while(true)		{   			int j,c;			//从最后到插入位置的所有索引项都后移一个位置			for(j=p.keyNum;j>=i;j--)			{   				p.key[j+1]=p.key[j];				p.rec[j+1]=p.rec[j];				p.ptr[j+1]=p.ptr[j];			}			//把一个插入索引项(k,num,ap)放入节点p的i位置			p.key[i]=k;p.rec[i]=num;p.ptr[i]=ap;						p.keyNum++;						if(p.keyNum<=m-1)			{   				p.key[p.keyNum+1]=MaxKey;				return true;			}						//计算m/2的上整			c=(m%2!=0?(m+1)/2:m/2);			//建立新分裂的结点，该结点含有m-c个索引项			ap=new BayerTreeNode();			ap.keyNum=m-c;ap.parent=p.parent;			for(j=1;j<=ap.keyNum;j++)//复制关键字和记录项			{   				ap.key[j]=p.key[j+c];				ap.rec[j]=p.rec[j+c];			}			for(j=0;j<=ap.keyNum;j++)//复制指针			{   				ap.ptr[j]=p.ptr[j+c];				if(ap.ptr[j]!=null)					ap.ptr[j].parent=ap;//修改副指针			}						ap.key[m-c+1]=MaxKey;//最大值放入所有关键字后									//修改p节点关键字个数			p.keyNum=c-1;			//建立新的待向双亲结点插入的索引项(k,num,ap)			k=p.key[c];num=p.rec[c];			//在p结点最后放入最大关键字			p.key[c]=MaxKey;			//建立新的树根结点			if(p.parent==null)			{   				bt=new BayerTreeNode();				bt.keyNum=1;bt.parent=null;				bt.key[1]=k;bt.key[2]=MaxKey;				bt.rec[1]=num;				bt.ptr[0]=p;bt.ptr[1]=ap;				p.parent=ap.parent=bt;				return true;			}			//求出新的索引项(k,num,ap)在双亲结点的插入位置			p=p.parent;			i=1;			while(((Comparable)k).compareTo(p.key[i])>0)					i++;			}														}