算法导论 第十八章；B 树_算法导论 第18章答案

       B树是为磁盘或其他直接存取辅助存储设备而设计的一种平衡查找树。B树的”分支因子“可能很大，即每个节点可以有很多子女。这一因子由所用磁盘特性所决定，并且可以降低磁盘I/O操作次数。许多数据库系统都使用B树或B树的变形来存储信息。

B树结构形式如下:

其特点：

1）每个节点x有以下域：

a)  x.n:当前存储在节点x中的关键字

b) x.n 个key值，以非降序顺序存放，即 x.key(1) ≤ x.key(2) ≤ ... ≤ x.key(x.n)

c) x.leaf：bool型，若为叶子节点 x.leaf=TRUE,反之为FALUSE

2） 每个节点x包含x.n+1个指向其子女的指针x.c(1),x.c(2),...x.c(x.n+1)。（叶子节点无此域）

3）各关键字x.key(i)对存储在各子树中的关键字范围加以分隔：如果k(i)为存储在x.c(i)为根的子树中的关键字，则：

        

4） 每个叶子节点具有相同的深度，即树的高度 h

5） 每个节点包含的key数有一个上界和下界，这些界可以用一个称为B树的最小度数的固定整数 t ≥ 2 来表示：

a) 每个非根的节点必须至少有t-1个 key. 每个非根内节点至少有t个子女。如果树非空，则根节点至少包含一个key.

b) 每个节点可包含至多2t-1个key。所以一个内节点至多可能有2t个子女。如果一个节点恰好有2t-1个key,则称该点是满的。

6）如果n ≥ 1，则对任意的一棵包含n个关键字，高度为h,最小度t ≥ 2的B树T，有：

             

B树插入和搜索操作的完整代码如下：

#include<iostream>
#include<cstdlib>
#include<cstring>
#define Disk_Write(x)
#define Disk_Read(x)
#define t 2
#define N 2*t
using namespace std;
 
typedef struct BTNode{
	int n;           //the number of keys storing in the current node
	char key[N];     //N keys storing in nondecreasing order
	bool leaf;       //TRUE:left;FALSE:internal node
	BTNode *c[N+1];  //point n+1 children
	}BTNode;
 
typedef struct BTree{
	BTNode *root;
	}BTree;
 
void BTree_Print(BTNode *x)
{
	for(int i=1;i<=x->n;i++)
	{
		if(x->leaf == false)
			BTree_Print(x->c[i]);
		cout<< x->key[i]<<"  ";
	 	} 
	if(x->leaf == false)
		BTree_Print(x->c[x->n+1]);
	}
 
void BTree_SplitChild(BTNode *x,int i)
{
	BTNode *z=new BTNode();
	BTNode *y=x->c[i];   //split y (2t-1 keys) into y (t-1 keys) and  z(t-1 keys)
	z->leaf=y->leaf;
	z->n=t-1;
	for(int j=1 ; j<=t-1 ; j++)
		z->key[j]=y->key[t+j];
 
	if(y->leaf==false)//if y has children ,copy its children to z
		for(int j=1; j<=t; j++)
			z->c[j]=y->c[j+t];
	y->n=t-1;
 
	//let z become the (i+1)th child of x
	for(int j=x->n+1; j>=i+1; j--)
		x->c[j+1]=x->c[j];
	x->c[i+1]=z;
	
	//insert the (t)th key of y into (i)th index of x
	for(int j=x->n; j>=i; j--)
	   x->key[j+1]=x->key[j];
	x->key[i]=y->key[t];
	x->n++;
 
	Disk_Write(y);
	Disk_Write(z);
	Disk_Write(x);		
	}
void BTree_Insert_Nonfull(BTNode *x,char k)
{
	int i=x->n;
	if(x->leaf)
	{//x node is leaf
		while(i>=1 && k < x->key[i])  //search for the insert index
		{
			x->key[i+1]=x->key[i];
			i--;
		 	}
		//insert key
		x->key[i+1]=k;
		x->n++;
		Disk_Write(x);
		} 
	else   // x node is not leaf
	{ 
		while(i>=1 && k < x->key[i])
			i--;
		i++;
	//Read its child,and insert the key into its child node
	Disk_Read(x->c[i]);
	//case 1: the child is full
	if(x->c[i]->n == 2*t-1)
	{
		BTree_SplitChild(x,i);
		if(k > x->key[i])
			i++;
		}
	//case 2:the child is not full
	BTree_Insert_Nonfull(x->c[i],k);
	}
}
void BTree_Insert(BTree *T,char k)
{
	BTNode *r=T->root;
	if(r->n == 2*t-1)
	{//root node is full
		//a new node s becomes the root
		BTNode *s=new BTNode(); 
		T->root=s;
		s->leaf=false;
		s->n=0;
		s->c[1]=r;
		//split the original root into two chilren of s
		BTree_SplitChild(s,1);
		//insert the key into the nonfull node
		BTree_Insert_Nonfull(s,k);
		}
		else//root node is not full
			BTree_Insert_Nonfull(r,k); //insert key into root node directly
	}
BTNode *BTree_Search(BTNode *x,char k,int &i)
{//return pair(y,i)consisting of a node y and an index i such that y.keyi=k
	 i=1;
	while(i <= x->n && k > x->key[i])
		i++;
	if(i <= x->n && k == x->key[i])
		return x;
	else if(x->leaf)
	{     
		i=0;
		return NULL;
		}
	else
	{  
		Disk_Read(x->c[i]);
		return BTree_Search(x->c[i],k,i);
	 	} 
	}
 
void BTree_Create(BTree *T,string ch)
{
	//first,create an empty root node
	BTNode *x=new BTNode();
	x->leaf=true;
	x->n=0;
 
	Disk_Write(x);
	T->root=x;
 
 
	//second,add new keys into T by calling Insert method
	for(int i=0;i<ch.length();i++)     
		BTree_Insert(T,ch[i]);      	
	}
 
void BTree_PrintDetail(BTNode *x)
{
	
	cout<<"The root is:";
	for(int i=1;i<=x->n;i++)
		cout<<x->key[i]<<"  ";
	cout<<endl;
	
	cout<<"The root's child is:"<<endl;
	for(int j=1;j<=x->n+1;j++)
	  {
		BTNode *child=x->c[j];
		for(int i=1;i<=child->n;i++)
			cout<<child->key[i]<<"   ";
		cout<<endl;
		}
	
	for(int i=1;i<=x->n+1;i++)
	{ 
		cout<<"The "<<i<<" child"<<endl;
		BTNode *child0=x->c[i];
		int m=child0->n+1;
		for(int j=1;j<=m;j++)
	 	{
			BTNode *c1=child0->c[j];
			for(int jj=1;jj<=c1->n;jj++)
				cout<<c1->key[jj]<<"  ";
			cout<<endl;
			}
		}
}
 
int main()
{	
	//string test_ch={'F','S','Q','K','C','L','H','T','V','W','M','R','N','P','A','B','X','Y','D','Z','E'};
	string test_ch="FSQKCLHTVWMRNPABXYDZE";
	cout<<"/*----------------------------Create B-tree---------------------------*/"<<endl;
	BTree *T=new BTree();
	BTree_Create(T,test_ch);       
	cout<<"After creating ,the B-tree(its degree is "<<t<<"):"<<endl;	
	BTree_Print(T->root);
	cout<<endl;
	cout<<"The detail B-tree is:"<<endl;
	BTree_PrintDetail(T->root);
	cout<<"/*--------------------------------------------------------------------*/"<<endl;
	
	cout<<"/*---------------------------Insert B-tree----------------------------*/"<<endl;
	char ich;
	cout<<"Please input the inserting char:";
	cin>>ich;
	BTree_Insert(T,ich);
	cout<<"After inserting ,the B-tree:"<<endl;
	BTree_Print(T->root);
	cout<<endl;
 
	cout<<"The detail of B-tree is:"<<endl;
	BTree_PrintDetail(T->root);
	cout<<"/*---------------------------------------------------------------------*/"<<endl;
	
	cout<<"/*--------------------------Search B-tree------------------------------*/"<<endl;
	char sch;
	BTNode *sNode=NULL;
	int index;
	cout<<"Please input the searching char:";
	cin>>sch;
	sNode=BTree_Search(T->root,sch,index);
	if(sNode==NULL)
		cout<<"The key doesn't exist in the B-tree."<<endl;
	else
	{ 
		cout<<"The key in the Node:";
		for(int i=1;i<=sNode->n;i++)
			cout<<sNode->key[i]<<"  ";
		cout<<endl;
		cout<<"The index of the key in the node is:"<<index<<endl;
		} 
	cout<<"/*---------------------------------------------------------------------*/"<<endl;
 
 
	return 0;
	}

运行结果：

【注：若有错误，请指正~~~】