avl.cpp

演示了AVL的删除与插入算法

#include "AVL.H"

void OperationAvl::LL(Avlnode*&p,Avlnode*&s,Avlnode*&r)
{
	s->bf+=r->bf;
	r->bf+=1;
	p=r;
	r=p->rchild;
	p->rchild=s; 
	s=p;
}

void OperationAvl::LR(Avlnode*&p,Avlnode*&s,Avlnode*&r)
{
	Avlnode* pp;
	pp=p;
	p=pp->lchild;
	pp->lchild=r;
	r=pp->rchild;
	pp->rchild=s;
	switch(pp->bf)
	{
		case -1:
			pp->lchild->bf= 0;
			pp->rchild->bf=1;
			pp->bf=0;
			break;
		case +1:
			pp->lchild->bf=-1;
			pp->rchild->bf=0;
			pp->bf=0;
			break;
		case  0:
			pp->lchild->bf= 0;
			pp->rchild->bf=0;
			break;
	}
	s=pp;
}

void OperationAvl::RL(Avlnode*&p,Avlnode*&s,Avlnode*&r)
{
	Avlnode* pp;
	pp=p;
	p=pp->rchild;
	pp->rchild=r;
	s->rchild=pp->lchild;
	pp->lchild=s;
	switch(pp->bf)
	{
		case -1:
			(pp->rchild)->bf=1;
			(pp->lchild)->bf= 0;
			pp->bf=0;
			break;
		case +1:
			(pp->rchild)->bf=0;
			(pp->lchild)->bf=-1;
			pp->bf=0;
			break;
		case  0:
			(pp->rchild)->bf=0;
			(pp->lchild)->bf= 0;
			break;
	}
	s=pp;
}

void OperationAvl::RR(Avlnode*&p,Avlnode*&s,Avlnode*&r)
{
	s->bf-=r->bf;
	r->bf-=1;
	p=r;
	r=p->lchild;
	p->lchild=s;
	s=p;
}

bool OperationAvl::Avl_in(std::string data)
{
	Avlnode *s,*r,*q,*t = NULL,*p = NULL;
	Avlnode *as,*aq;
	s = tree_root;
	if(s == NULL)
	{
		as = new Avlnode;
		as->bf = 0;
		as->data = data;
		as->lchild = as->rchild = NULL;
		tree_root = as;
		return true;
	}

	q = s;
	while((q != NULL)&&(q->data != data))
	{
		if(q->bf)
		{
			t = p;
			s = q;
		}
		p = q ;
		if(data < q->data)
			q = q->lchild;
		else
			q = q->rchild;
	}
	if(q != NULL)
		return false;

	aq = new Avlnode;
	q = aq;
	q->data = data;
	q->lchild = q->rchild = NULL;
	q->bf = 0;

	if(data < p->data) p->lchild = aq;
	else p->rchild = aq;

	if(data<s->data) r = s->lchild;
	else r = s->rchild;

	p = r;
	while(p != q)
	{
		if(data < p->data)
		{
			p->bf = -1;
			p = p->lchild;
		}
		else
		{
			p->bf = 1;
			p = p->rchild;
		}
	}
	switch(s->bf)
	{
	case 0:
		if(data < s->data)
			s->bf = -1;
		else
			s->bf = 1;
		break;
	case -1:
		if(data>s->data)
		{
			s->bf = 0;
		}
		else if(r->bf<0)
		{
			if(t = NULL)
				LL(as,tree_root,s->lchild);
			else if(s->data < t->data)
				LL(as,t->lchild,s->lchild);
			else
				LL(as,t->rchild,s->lchild);
		}
		else
		{
			if(t == NULL)
				LR(r->rchild,tree_root,s->lchild);
			else if(s->data < t->data)
				LR(r->rchild,t->lchild,s->lchild);
			else
				LR(r->rchild,t->rchild,s->lchild);
		}
		break;
	case 1:
		if(data < s->data)
			s->bf = 0;
		else if(r->bf >0)
		{
			if(t == NULL)
				RR(as,tree_root,s->rchild);
			else if(s->data<r->data)
				RR(as,t->lchild,s->rchild);
			else
				RR(as,t->rchild,s->rchild);			
		}
		else
		{
			if(t ==NULL)
				s->bf = 0;
			else if(r->bf>0)
			{
				if(t == NULL)
					RR(as,tree_root,s->rchild);
				else if(s->data < t->data)
					RR(as,t->lchild,s->rchild);
				else
					RR(as,t->rchild,s->rchild);
			}
			else
			{
				if(t == NULL)
					RL(r->lchild,tree_root,s->rchild);
				else if(s->data < t->data)
					RL(r->lchild,t->lchild,s->rchild);
				else
					RL(r->lchild,t->rchild,s->rchild);
			}
		}
		break;
	}
	return true;
}

bool OperationAvl::Avl_find(std::string data,Avlnode*& find)
{
	Avlnode *p, *q;
	q = tree_root;
	p = NULL;
	while(q&&q->data != data)
	{
		p = q;
		if(q->data > data)
			q = q->lchild;
		else
			q = q->rchild;
	}
	if(q == NULL)
		return false;
	else
	{
		find = q;
		return true;
	}
}

bool OperationAvl::Avl_out(std::string data)
{
	bool inf = false;
	Avlnode *p,*q,*r,*s,*t,*as;
	stack<Avlnode*> st;
	s = tree_root;
	if(s == NULL) return false;

	p = NULL;
	q = s;
	while((q != NULL)&&(data != q->data))
	{
		p = q;
		st.push(q);
		if(data > q->data)	q = q->rchild;
		else	q = q->lchild;
	}
	if(q == NULL)	return false;
	if((q->lchild)&&(q->rchild))
	{
		t = q;
		p = q;
		st.push(q);
		if(q->bf<=0)
		{
			q = q->lchild;
			while(q)
			{
				p = q;
				st.push(q);
				q = q->rchild;
			}
		}
		else 
		{
			q = q->rchild;
			while(q)
			{
				p = q;
				st.push(q);
				q = q->lchild;
			}
		}
		t->data = p->data;
		data = p->data;
		q = p;
		p = st.top();
		st.pop();
	}

	if((q->lchild == NULL)&&(q->rchild == NULL))
	{
		if(p == NULL)
		{
			delete tree_root;
			tree_root = NULL;
		}
		else if(data < p->data)
		{
			delete p->lchild;
			p->lchild = NULL;
		}
		else if(data == p->data)
		{
			if(p->bf <= 0)
			{
				delete p->lchild;
				p->lchild = NULL;
			}
			else
			{
				delete p->rchild;
				p->rchild = NULL;
			}
		}
		else
		{
			delete p->rchild;
			p->rchild = NULL;
		}
	}
	else
	{
		as = q->rchild;
		if(p == NULL)	tree_root = as;
		else if(data < p->data)	p->lchild = as;
		else if(data == p->data)
		{
			if(p->bf <= 0) p->lchild = as;
			else p->rchild = as;
		}
		else p->rchild = as;
	}
	inf = true;
	while((st.empty() != true)&&(inf == true))
	{
		s = st.top();
		st.pop();
		if(st.empty() == true)	t = NULL;
		else	t = st.top();
		if((data < s->data)||(data == s->data)&&(s->bf <= 0))
			switch(s->bf)
			{
				case 0:
					s->bf = 1;
					inf = false;
					break;
				case -1:
					s->bf = 0;
					break;
				case +1:
					r = s->rchild;
					if(r->bf>=0)
					{
						if(r->bf == 0)	inf = false;
						if(t == NULL)	RR(as,tree_root,s->rchild);
						else if(s->data < t->data)	RR(as,t->lchild,s->rchild);
						else	RR(as,t->rchild,s->rchild);
					}
					else if(r->bf == -1)
					{
						if(t == NULL)	RL(r->lchild,tree_root,s->rchild);
						else if(s->data < t->data)	RL(r->lchild,t->lchild,s->rchild);
						else RL(r->lchild,t->rchild,s->rchild);
					}
					break;
			}
		else
			switch(s->bf)
			{
				case 0:
					s->bf = -1;
					inf = false;
					break;
				case 1:
					s->bf = 0;
					break;
				case -1:
					r = s->lchild;
					if(r->bf <= 0)
					{
						if(r->bf == NULL)	inf =false;
						if(t == NULL)	LL(as,tree_root,s->lchild);
						else if(s->data < t->data)	LL(as,t->lchild,s->lchild);
						else	LL(as,t->rchild,s->lchild);
					}
					else
					{
						if(t == NULL)	LR(r->rchild,tree_root,s->lchild);
						else if(s->data < t->data)	LR(r->rchild,t->lchild,s->lchild);
						else	LR(r->rchild,t->rchild,s->lchild);
					}
					break;
			}
	}
	return true;
}

void OperationAvl::show(Avlnode* root)
{
	if(root)
	{
		show(root->lchild);
		cout<<root->data<<" ";
		show(root->rchild);
	}
}

void OperationAvl::Avl_show()
{
	if(tree_root != NULL)	show(tree_root);
	else	cout<<"空树，待插入！";
	cout<<'\n';
}

void OperationAvl::mclear(Avlnode* root)
{
	if(root)
	{
		mclear(root->lchild);
		clear.push(root);
		mclear(root->rchild);
	}
}

void OperationAvl::Avl_clear()
{
	Avlnode* p;
	mclear(tree_root);
	if(tree_root != NULL)
	{
		while(clear.size()!=0)
		{
			p = clear.top();
			clear.pop();
			delete p;
		}
		tree_root = NULL;
		cout<<"清空成功＾_＾";
	}
	else cout<<"树已空~_~";
	cout<<'\n';
}