btree.cpp

代码注重B树插入、删除的算法逻辑

#include "BTree.h"

pBTreeNode t = new BTreeNode[K];//自定义的虚拟堆栈；

bool Queue::push(pBTreeNode x)
{
	if(size == K)
		return false;

	rear = (++rear) % K;
	que[rear] = x;
	size ++;
	if(size == 1 && front == -1)
		front = 0;
	return true;
}

pBTreeNode Queue::getfront()
{
	pBTreeNode x;
	if(size == 0)
		x =NULL;

	else
	{
		x = que[front++];
		front = front % K;
		size --;
		if(size == 0)
			front = rear = -1;
	}
	return x;
}

int BTree::BSearch(KeyType k,pBTreeNode* p)
{
	pBTreeNode q;
	int i;
	*p = q = T;
	while((q != NULL)  && (q->keynum != 0))
	{
		*p = q;
		q->key[0] = k;
		for(i = q->keynum;k < q->key[i] ; i--)	;
		if(q->key[q->keynum] == k)
			return q->keynum;
		/*if(i > 0 && q->key[i+1] == k)
			return i+1;*/
		if(i > 0 && q->key[i] == k)
			return i;
		/*if(i == q->keynum && q->key[i] < k && q->ptr[0] == NULL)
			return q->keynum + 1;*/
		

		q = q->ptr[i];
	}
	return 0;
}

pBTreeNode BTree::Insert(KeyType k,bool& torf)
{
	bool mark = false;
	pBTreeNode p, sl = NULL, sr = NULL;
	int i;
	if(BSearch(k,&p))
	{
		torf = false;
		return T;
	}
	while(p != NULL)
	{
		p->key[0] = k;
		for(i = p->keynum;k < p->key[i];i--)
		{
			mark = true;
			p->key[i+1] = p->key[i];
			p->ptr[i+1] = p->ptr[i];
		}
		if(mark == false)
		{i = p->keynum + 1;}
		else	i++;
		p->key[i] = k;
		p->ptr[i-1] = sl;
		p->ptr[i+1] = sr;
		if(++(p->keynum) < M)
			break;

		else
		{
			sr = split(p);
			sl = p;
			k = p->key[p->keynum+1];
			p = p->parent;
		}//else
	}//while

	if(p == NULL)
	{
		p = ++t;
		p->keynum = 1;
		p->key[1] = k;
		p->ptr[0] = sl;
		p->ptr[1] = sr;
		T = p;
		torf = true;
		return p;
	}
	else 
	{
		torf = true;
		return T;
	}
}

int BTree::MoveKey(pBTreeNode& p)
{
	pBTreeNode b,f = p->parent;//f:father b:brother
	int i,j;
	for(i = 0;f->ptr[i] != p ;i++)
		;

	if(i > 0)
	{
		b = f->ptr[i - 1];
		if(b->keynum > (m-1)/2)
		{
			for(j = p->keynum;j >= 0;j--)
			{
				p->key[j+1] = p->key[j];
				p->ptr[j+1] = p->ptr[j];
			}
			p->key[1] = f->key[i];
			f->key[i] = b->key[b->keynum];
			p->ptr[0] = b->ptr[b->keynum];
			p->keynum++;
			b->keynum--;
			return 1;
		}

		if(i < f->keynum)
		{
			b = f->ptr[i+1];
			if(b->keynum > (m-1)/2)
			{
				p->key[p->keynum] = f->key[i+1];
				f->key[i+1] = b->key[1];
				p->ptr[p->keynum] = b->ptr[0];
				for(j = 0;j< b->keynum;j++)
				{
					b->key[j] = b->key[j+1];
					b->ptr[j] = b->ptr[j+1];
				}
				p->keynum++;
				b->keynum--;
				return 1;
			}
		}
	}
	return 0;
}

pBTreeNode BTree::split(pBTreeNode& p)
{
	int i , mid ,j;
	pBTreeNode New = ++t;
	mid = (m+1)/2;
	New->ptr[0] = p->ptr[mid];
	j = 1;
	for(i = mid + 1;i <= m ; i++)
	{
		New->key[j] = p->key[i];
		New->ptr[j++] = p->ptr[i];
	}
	New->keynum = m - mid;
	p->keynum = mid - 1;
	return New;
}

pBTreeNode BTree::Bmerge(pBTreeNode& p)
{
	pBTreeNode b,f = p->parent;
	int i,j;
	for( i = 0;f->ptr[i] != p;i++)
		;

	if(i > 0)
		b = f->ptr[i-1];
	else
	{
		b = p;
		p = f->ptr[i + 1];
	}

	b->key[++b->keynum] = f->key[i];
	b->ptr[b->keynum] = p->ptr[0];

	for(j = 1;j <= p->keynum ; j++)
	{
		b->key[++b->keynum] = p->key[j];
		b->ptr[b->keynum] = p->ptr[j];
	}
	t--;
	p = NULL;

	for( j = i + 1;j<f->keynum ; j++)
	{
		f->key[j-1] = f->key[j];
		f->ptr[j-1] = f->ptr[j];
	}
	f->keynum--;
	return b;

}


bool BTree::Delete(KeyType k)
{
	pBTreeNode p,s;
	int i,j;
	i = BSearch(k,&p);
	if( i == 0) return 0;
	if( i > 0 && p->ptr[i-1])
	{
		if(p->ptr[i-1]->keynum != 0)
		{
			s = p->ptr[i-1];
			while(s->ptr[s->keynum])
				s = s->ptr[s->keynum];

			p->key[i] = s->key[s->keynum];
			p = s;
			i = s->keynum;
		}
	}
	for(j = i + 1; j <= p->keynum ; j++)
	{
		p->key[j-1] = p->key[j];
	}

	p->keynum--;

	while(p->keynum < (m-1)/2 && p->parent)
	{
		if(!MoveKey(p))
			p = Bmerge(p);
		p = p->parent;
	}
	if( p == T && T->keynum == 0)
	{
		if(T->ptr[0] != NULL)// && (T->ptr[0]->keynum != 0))
		{
			if(T->ptr[0]->keynum != 0)
			{
				T = T->ptr[0];
				t--;
				p = NULL;
			}
		}
		else
		{
			if(p != NULL)
			{t--;}
			T = NULL;
		}
	}
	return 1;
	
}

void BTree::show()
{
	pBTreeNode s;
	int num;
	int j = 0;
	Queue q;
	if((T != NULL) && (T->keynum != 0))
	{
		q.push(T);
		while(q.empty() == false)
		{
			s = q.getfront();
			if(s != NULL)
			{
				num = s->keynum;
				if((num != 0) && (s->ptr[0] != NULL))
				{
					q.push(s->ptr[0]);
				}
				if(num != 0)
				{
					for(j = 1; j <= num; j++)
					{
						if(s->ptr[j] != NULL)
						{q.push(s->ptr[j]);}
						cout<<s->key[j]<<" ";
					}
					cout<<" ";
				}
			}
			else
				break;
		
		}
		cout<<endl;
	}
	
	else
		cout<<"Ｂ树为空树，有待插入！"<<endl;
}


void command()
{
	std::cout<<"说明："<<endl;
	std::cout<<"	本程序演示了B-树的插入和删除。"<<endl;
	std::cout<<"	本程序模拟了DOS的命令行，各有效命令见下："<<endl;
	std::cout<<"	add：插入一个结点； del：删除一个结点；"<<endl;
	std::cout<<"	quit/exit：退出程序；show：显示已经插入的节点的关键字。"<<endl;
	std::string str;
	KeyType k;
	bool exitif = false;

	//t->keynum = 0;
	//t->key[1] = '\0';

	BTree btree;
	while(!exitif)
	{
		std::cout<<">>";
		std::cin>>str;
		if(str == "exit")
			exitif = true;

		else if(str == "quit")
			exitif = true;

		
		else if(str == "add")
		{
			std::cin>>k;
			bool torf = false;
			btree.Insert(k,torf);
			if(torf)
				cout<<"插入成功!"<<endl;
			else 
				cout<<"插入失败!"<<endl;
		}

		else if(str == "del")
		{
			std::cin>>k;
			if(btree.Delete(k))
				cout<<"删除成功!"<<endl;
			else
				cout<<"删除失败!"<<endl;
		}

		else if(str == "show")
		{
			btree.show();
		}

		else
		{
			std::cout<<str<<"不是内部命令，请仔细阅读说明。"<<endl;
		}
	}
}

int main()
	{
	command();
	return 0;
}