B-樹
B-樹的查找
B-樹的插入
//演算法7.8 B-樹的查找
//演算法7.9 B-樹的插入
#include<iostream>
using namespace std;
#define FALSE 0
#define TRUE 1
#define OK 1
#define m 3 //B-樹的階，暫設為3
typedef struct BTNode{
int keynum; //結點中關鍵字的個數，即結點的大小
BTNode *parent; //指向雙親結點
int key[m+1]; //關鍵字矢量，0號單元未用
BTNode *ptr[m+1]; //子樹指標矢量
}BTNode,*BTree;
//- - - - - B-樹的查找結果型別定義- - - - -
struct Result{
BTNode *pt; //指向找到的結點
int i; //1..m，在結點中的關鍵字序號
int tag; //1：查找成功，0：查找失敗
};
int Search(BTree T,int key)
{
BTree p=T;
int endnum;
if(p) //樹不為空時
{
endnum=p->keynum; //獲得首節點包含的記錄個數
}
else
{
return 0; //回傳沒找到
}
int i=0;
if(endnum==0)
{
return i; //樹存在，但僅有一個為空根節點
}
else if(key>=p->key[endnum])//節點不為空，但當前值比最大的key還大
{
i=endnum;
return i;
}
else if(key<=p->key[1]) //節點不為空，但當前值比最小的key還小
{
return i;}
else
{
for(i=1;i<endnum;i++) //有合適的位置，即處于當前結點的最大和最小值之間，或找到了
{
if(p->key[i]<=key && key<p->key[i+1])
return i;
}
}
}
void Insert(BTree &q,int i,int x,BTree &ap)
{//將x插入q結點的i+1位置中
int j;
for(j=m-1;j>i;j--)
{
//將插入位置之后的key全部后移一位
q->key[j+1]=q->key[j];
}
for(j=m;j>i;j--)
{
//相應地也移動其后ptr的位置
q->ptr[j]=q->ptr[j-1];
}
q->key[i+1]=x;//插入x到該位置
q->ptr[i+1]=ap;
q->keynum++;
}
void split(BTree &q,int s,BTree &ap)
{ //將q->key[s+1,..,m], q->ptr[s+1,..,m]移入新結點*ap作為右結點
//原結點作為新的左側結點
//中間值被保存在ap[0]->key中，等待找到跳轉回InsertBTree（）尋找到到合適的插入位置插入
int i;
ap=new BTNode;
for(i=s+1;i<=m;i++)
{ //將q->key[s+1,..,m]保存到ap->key[0,..,m-s+1]中
//將q->ptr[s+1,..,m]保存到ap->ptr[0,..,m-s+1]中
ap->key[i-s-1]=q->key[i];
ap->ptr[i-s-1]=q->ptr[i];
}
if(ap->ptr[0])
{
//當ap有子樹的時候
for(i=0;i<=1;i++)
{
//將ap的子樹的父親改為ap自己
ap->ptr[i]->parent=ap;
}
}
ap->keynum=(m-s)-1;
ap->parent=q->parent;//將ap的父親改為q的父親
q->keynum=q->keynum-(m-s);//修改q的記錄個數
}
void NewRoot(BTree &T,BTree q,int x,BTree &ap)//生成含資訊（T, x, ap）的新的根結點*T，原T和ap為子樹指標
{
BTree newT=new BTNode;//新建一個結點作為新的根
newT->key[1]=x;//寫入新根的key[1]
newT->ptr[0]=T;//將原來的樹根作為新根的左子樹
newT->ptr[1]=ap;//ap作為新根的右子樹
newT->keynum=1;
newT->parent=NULL;//新根的父親為空
ap->parent=newT;//ap的父親為新根
T->parent=newT;//T的父親為新根
T=newT;//樹改成新根引導的
}
//演算法7.9 B-樹的插入
int InsertBTree(BTree &T,int K,BTree q,int i){
int x=K;
BTree ap=NULL;
int finished=FALSE;//x表示新插入的關鍵字，ap為一個空指標
while(q&&!finished){
Insert(q,i,x,ap); //將x和ap分別插入到q->key[i+1]和q->ptr[i+1]
if (q->keynum<m)
finished=TRUE; //插入完成
else{ //分裂結點*q
int s= m/2;
split(q,s,ap);
x=ap->key[0];// x=q->key[s];
//將q->key[s+1..m], q->ptr[s..m]和q->recptr[s+1..m] 移入新結點*ap
q=q->parent;
if(q)
{
i=Search(q,x);
} //在雙親結點*q中查找x的插入位置
} //else
} //while
if(!finished) //T是空樹（引數q初值為NULL）或者根結點已分裂為結點*q和*ap
NewRoot(T,q,x,ap); //生成含資訊（T, x, ap）的新的根結點*T，原T和ap為子樹指標
return OK;
} //InsertBTree //InsertBTree
//演算法7.8 B-樹的查找
Result SearchBTree(BTree &T, int key){
/*在m階B-樹T上查找關鍵字key，回傳結果(pt,i,tag)，若查找成功，則特征值tag=1，指標pt所指結點中第i個關鍵字等于key；否則特征值tag=0，等于key的關鍵字應插入在指標pt所指結點中第i和第i+1個關鍵字之間*/
BTree p=T;
BTree q=NULL;
int found=FALSE;
int i=0; //初始化，p指向待查結點，q指向p的雙親
while(p&&!found){
i=Search(p,key);
//在p-＞key[1..keynum]中查找i，使得：p-＞key[i]＜=key＜p-＞key[i+1]
if(i>0&&p->key[i]==key)
found=TRUE; //找到待查關鍵字
else
{
q=p;
p=p->ptr[i];
}
}
Result result;
if(found)
{
result.pt=p;
result.i=i;
result.tag=1;
return result;
} //查找成功
else
{
result.pt=q;
result.i=i;
result.tag=0;
return result;
} //查找不成功，回傳K的插入位置資訊
}//SearchBTree
void InitialBTree(BTree &T)
{
//初始化一個空的根
T->keynum=0;
T->parent=NULL;
for(int i=0;i<m+1;i++)
{
T->ptr[i]=NULL;
}
}
void main()
{
BTree T=new BTNode;
InitialBTree(T);
//先用SearchBTree()找到要插入的位置，得到一個Result結構體
//再用InsertBTree()插入資料
Result result;
int a[11]={45,24,53,90,3,12,50,61,70,100};
for(int i=0;i<10;i++)
{
result=SearchBTree(T,a[i]);
if(result.tag==0)
{
InsertBTree(T,a[i],result.pt,result.i);
}
}
cout<<"OK";
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/115738.html
標籤：其他