#include "Btree.h"
#include <iostream>
#include <math.h>
#include <stack>
using namespace std;
void Btree::InsertBtree(int k)
{
if (!root)
{
root=new TreeNode(0,k,0);
return ;
}
TreeNode *a=root;/*当前节点*/
int i=1;/*k关节字 要插入节点a 的位置索引*/
/*找到插入节点*/
while(a)
{
i=1;
/*在a 中找到第一个比关键字k大的关键字的位置 i */
while(i<=a->keynum)
{
if (k<=a->key[i])
break;
else
i++;
}
/* 判断是否继续向下 还是已经到达子节点 */
if (!a->ptr[i-1])/* 已是叶子节点无需向下 直接插入 */
break;
else/*不是叶子节点*/
a=a->ptr[i-1];
}
if (a->key[i]==k)/*该关键字节点已存在 */
return ;
Insert(k,0,a);/*在叶子节点中插入关键字k*/
}
void Btree::Insert(int k,TreeNode* node,TreeNode* a)/*关键字：k 该关键字k的右子树指针 插入节点a */
{
int i=1;
/*在a 中找到第一个比关键字k大的关键字的位置 i */
while(i<=a->keynum)
{
if (k<=a->key[i])
break;
else
i++;
}
/*插入节点为 a 索引为 i */
for (int j=a->keynum;j>=i;j--)/*向后移动以便插入新关键字*/
{
a->key[j+1]=a->key[j];/* 关键字*/
a->ptr[j+1]=a->ptr[j];/*子树指针*/
}
a->key[i]=k;
a->ptr[i]=node;
a->keynum++;
if (a->keynum<=m-1) return;
else
{/*分裂节点然后插入父节点 |1 2 3 ...|ceil(m)(向上取整)|... m| */
int midkey=a->key[(int)ceil(m/2.0)];/*中间关键字及 NewNode 要插入父节点*/
TreeNode* NewNode=new TreeNode(a->parent,a->key,a->ptr);/*和a同parent*/
/*
for (int i=0;i<=NewNode->keynum;i++)
{
if (NewNode->ptr[i])
NewNode->ptr[i]->parent=NewNode;
}*/
a->keynum=m-ceil(m/2.0);
TreeNode * tempa=a;/*记录当前节点*/
a=a->parent;/*父节点*/
if (!a)/*无父节点*/
{
TreeNode *NewRoot=new TreeNode(tempa,midkey,NewNode);
tempa->parent=NewRoot;
NewNode->parent=NewRoot;
root=NewRoot;
return;
}
else
Insert(midkey,NewNode,a);
}
}
Result Btree::Find(int k)
{
if (!root)
{
cout<<"the tree is null !"<<endl;
return Result(0,0,0);
}
TreeNode* a=root;
int i=1;
while(a)
{
i=1;
while(i<=a->keynum)
{
if (k<=a->key[i])
{
break;
}
else
{
i++;
}
}
if (k==a->key[i])
{
return Result(a,i,1);
}
else
{
if (!a->ptr[i-1])
{
return Result(a,i,0);
}
else
{
a=a->ptr[i-1];
}
}
}
}
void Btree::DeleteBtree(int k)
{
if (!root)
{
cout<<"The tree is null !"<<endl;
return;
}
/*转化为删除叶子节点中的关键字 找其右子树的最小关键字*/
stack<int> s;/*记录路径上的 所有 index */
TreeNode *delnode=root;//待删除关键字k所在节点
int i=1;
while (delnode&&delnode->keynum)/*delnode->keynum ==0 是对B+树而言*/
{
i=1;
while(i<=delnode->keynum)
{
if (k<=delnode->key[i])
{
break;
}
else
{
i++;
}
}
if (k==delnode->key[i])
{
break;/*找到了*/
}
else
{
if (delnode->ptr[i-1]==0)
{
/*无此关键字*/
cout<<"no this key :"<<k<<endl;
return ;
}
else
{
/*向下一层*/
delnode=delnode->ptr[i-1];
s.push(i-1);/*通过该索引的指针向下一层查找*/
}
}
}
/* delnode i parent可以提供回去的路 */
TreeNode *p=delnode;/*当前节点*/
if (delnode->ptr[i]&&delnode->ptr[i]->keynum)/*delnode 不是叶子节点*//*B+tree 的元素节点*/
{
s.push(i);
p=delnode->ptr[i];
while(p->ptr[0]&&p->ptr[0]->keynum)/* p到达delnode 的右子树中最小关键字节点*/
{
p=p->ptr[0];
if (!p->ptr[0]->keynum)
break;
s.push(0);
}
}
if (p!=delnode)
{
/*将删除操作到对叶子节点的关键字的删除*/
delnode->key[i]=p->key[1];
i=1;
}
/* p, i 删除关键字由delnode i 转换为 p i */
BorrowOrCombine(p,i,0,s);
}
void Btree::BorrowOrCombine(TreeNode *a,int i,int type,stack<int> &s)/*待处理关键字是a 节点的 i
type 标志此次操作的前一次是 对其左 -1 右 1 无0 孩子进行操作 即这是对叶子节点的操作*/
{
if (a==root&&root->keynum==1)
{
TreeNode * oldroot=root;
if (type==-1)
{
if (root->ptr[i])
root=root->ptr[i];
else
root=0;
}
else if (type==1)
{
if (root->ptr[i-1])
root=root->ptr[i-1];
else
root=0;
}
else/*不是由下层传递而来*/
{
root=0;
}
if(root)
root->parent=0;
delete oldroot;
return;
}
int minnum=ceil(m/2.0)-1;
TreeNode *la,*ra;/*a 的左右兄弟节点*/
// if (!a->ptr[0])/*a 为叶子节点*/
// {
TreeNode *pflag=a->ptr[i-1];/*对B+树 判断哪个元素节点被合并掉了 指针为0*/
if (a->keynum>minnum||a==root)
{
for (int j=i;j<a->keynum;j++)
{
a->key[j]=a->key[j+1];
if (type==-1)
{
a->ptr[j-1]=a->ptr[j];
}
else if (type==1)
{
a->ptr[j]=a->ptr[j+1];
}
else
{
/*这是对叶子节点的操作 B+树 而言*/
if (pflag)
{
a->ptr[j]=a->ptr[j+1];
}
else
{
a->ptr[j-1]=a->ptr[j];
}
}
}
if (!type&&!pflag)
{
a->ptr[j-1]=a->ptr[j];
}
if (type==-1)
{
a->ptr[j-1]=a->ptr[j];
}
a->key[j]=0;
a->ptr[j]=0;
a->keynum--;
return;
}
else
{/* aa->keynum=minnum */
int index=s.top();
s.pop();
/*能借则借 借优先*/
if (index)/*有左兄弟*/
{
la=a->parent->ptr[index-1];
if (la->keynum>minnum)/*左兄弟关键字足够多可以借*/
{
/* 从左兄弟借 */
/*向后移动覆盖 i */
for (int j=i;j>1;j--)
{
a->key[j]=a->key[j-1];
if (type==-1)
{
a->ptr[j-2]=a->ptr[j-1];
}
else if (type==1)
{
a->ptr[j-1]=a->ptr[j];
}
else
{
if (pflag)
{
a->ptr[j-1]=a->ptr[j];
}
else
{
a->ptr[j-2]=a->ptr[j-1];
}
}
}
if (!type&&pflag)
{
a->ptr[j-1]=a->ptr[j];
}
if (type==1)
{
a->ptr[j-1]=a->ptr[j];
}
a->key[j]=a->parent->key[index];
a->ptr[0]=la->ptr[la->keynum];/*左兄弟的最右子树*/
/*父节点改变*/
la->ptr[la->keynum]->parent=a;
a->parent->key[index]=la->key[la->keynum];
la->key[la->keynum]=0;
la->ptr[la->keynum]=0;
la->keynum--;
return;
}
}
if (index<a->keynum)/*有右兄弟index<=a->keynum*/
{
ra=a->parent->ptr[index+1];
if (ra->keynum>minnum)/*右兄弟关键字足够多可以借*/
{
/* 从右兄弟借 */
/*向前移动覆盖 i */
for (int j=i;j<a->keynum;j++)
{
a->key[j]=a->key[j+1];
if (type==-1)
{
a->ptr[j-1]=a->ptr[j];
}
else if (type==1)
{
a->ptr[j]=a->ptr[j+1];
}
else
{
if (pflag)
{
a->ptr[j]=a->ptr[j+1];
}
else
{
a->ptr[j-1]=a->ptr[j];
}
}
}
if (!type&&!pflag)
{
a->ptr[j-1]=a->ptr[j];
}
if (type==-1)
{
a->ptr[j-1]=a->ptr[j];
}
a->key[j]=a->parent->key[index+1];
a->ptr[j]=ra->ptr[0];/*右兄弟的最左子树*/
if (ra->ptr[0]) /*叶子节点的 -》ptr【0】==0*/
ra->ptr[0]->parent=a;
a->parent->key[index+1]=ra->key[1];
/*右兄弟关键字去头 前移*/
for (int t=1;t<ra->keynum;t++)
{
ra->ptr[t-1]=ra->ptr[t];
ra->key[t]=ra->key[t+1];
}
/*t= ra->keynum */
ra->ptr[t-1]=ra->ptr[t];
ra->key[t]=0;
ra->ptr[t]=0;
ra->keynum--;
return;
}
}
/*合并可能会使 不完善节点向上传递*/
if (index)/*有左兄弟*/
{
la=a->parent->ptr[index-1];
if (la->keynum==minnum)/*左兄弟关键字不够多*/
{
/* 合并到左兄弟 */
la->key[la->keynum+1]=a->parent->key[index];
/*a 中的关键字填充到其左兄弟中 0 1 2 .... i-1 | i | i+1 ...... kyenum */
for (int l=1;l<=i-1;l++)
{
la->key[la->keynum+l+1]=a->key[l];
la->ptr[la->keynum+l]=a->ptr[l-1];
/*子树的父节点改变*/
if(a->ptr[l-1])
a->ptr[l-1]->parent=la;
}
if (type==-1)
{
la->ptr[la->keynum+l]=a->ptr[l];
- 1
- 2
前往页