avltree.h

数据结构课程程序

/*
AVLTREE 1.01
The avltree and node classes.
Written by
Deepak  <[e-mail]>
http://www.geocities.com/acmesofties/
26-June-2002
avltree.zip 
Read the help.txt in the package for further
information.
*/


class node
{
public:
    int data;
    node *left,*right;
    int bf;
    node(int d)
    {
	data=d;
	left=NULL;
	right=NULL;
	bf=0;
    }
    node()
    {
	data=0;
	left=NULL;
	right=NULL;
	bf=0;
    }
};


class avltree
{
private:
    node *arr[100];
    int ac;
public:
    node *root;
    avltree()
    {
	root=NULL;
	ac=0;
    }
    void insert(int key)
    {
	node *t=root;
	node *p=new node(key);
	if(root==NULL)
	{
	    root=p;
	    return;
	}
	while(true)
	{
	    if(key==t->data)return;
	    if(key>t->data && t->right==NULL)
	    {
		t->right=p;
		break;
	    }
	    if(key<t->data && t->left==NULL)
	    {
		t->left=p;
		break;
	    }
	    if(key<t->data)
	    {
		t=t->left;
	    }
	    else
		t=t->right;
	}
	/*Balancing*/
	t=getnode(key);
	while(t!=NULL)
	{
	    int hd=balance(t);
	    if(fabs(hd)>1)
	    {
		if(hd<0)
		{
		    if(balance(t->left)<0)
		    {
			rightrotate(t);
		    }
		    else
		    {
			leftrotate(t->left);
			rightrotate(t);
		    }
		}
		else
		{
		    if(balance(t->left)>0)
		    {
			leftrotate(t);
		    }
		    else
		    {
			rightrotate(t->right);
			leftrotate(t);
		    }
		}
		break;
	    }
	    t=getparent(t->data);
	}
	return;
    }
    node *getinordersuccessor(node *t)
    {
	t=t->right;
	while(t->left!=NULL)t=t->left;
	return t;
    }
    void remove(int key)
    {
	node *t=getnode(key);
	if(t==NULL)return;
	node *q=getparent(key);
	if(t->left!=NULL && t->right!=NULL)
	{
	    /*For replacing with inorder successor*/
	    node *y=getinordersuccessor(t);
	    q=getparent(y->data);
	    t->data=y->data;
	    t=y;
	}
	node *p=NULL;
	if(q==NULL && t!=root)return;
	int rootchild=(q!=NULL && q==root)?1:0;
	int isroot=(t==root)?1:0;
	int i=(q!=NULL && q->left==t)?0:1;
	if(t->left==NULL && t->right==NULL)
	{
	    if(!isroot)
	    {
		if(!i)q->left=NULL;
		else q->right=NULL;
		delete t;
		p=q;
	    }
	    else
	    {
		root=NULL;
		delete t;
	    }
	}
	else if(t->left==NULL)
	{
	    if(!isroot)
	    {
		if(!i)q->left=t->right;
		else q->right=t->right;
		delete t;
		p=q;
	    }
	    else
	    {
		root=t->right;
		delete t;
	    }
	}
	else if(t->right==NULL)
	{
	    if(!isroot)
	    {
		if(!i)q->left=t->left;
		else q->right=t->left;
		delete t;
		p=q;
	    }
	    else
	    {
		root=t->left;
		delete t;
	    }
	}
	if(rootchild)root=p;
	/*Balancing part*/
	t=p;
	while(t!=NULL)
	{
	    int hd=balance(t);
	    if(fabs(hd)>1)
	    {
		if(hd<0)
		{
		    if(balance(t->left)<0)
		    {
			rightrotate(t);
		    }
		    else
		    {
			leftrotate(t->left);
			rightrotate(t);
		    }
		}
		else
		{
		    if(balance(t->left)>0)
		    {
			leftrotate(t);
		    }
		    else
		    {
			rightrotate(t->right);
			leftrotate(t);
		    }
		}
	    }
	    t=getparent(t->data);
	}
	return;
    }
    int height(node *t)
    {
	if(t==NULL)return 0;
	int hr=height(t->right);
	int hl=height(t->left);
	return 1+(hr>hl?hr:hl);
    }
    int balance(node *t)
    {
	if(t==NULL)return 0;
	return height(t->right)-height(t->left);
    }
    node *getparent(int key)
    {
	node *t=getnode(key);
	if(t==NULL || t==root)return NULL;
	node *t1=root;
	while(true)
	{
	    if(t1==NULL)return NULL;
	    if(t->data>t1->data && t->data==t1->right->data)return t1;
	    if(t->data<t1->data && t->data==t1->left->data)return t1;
	    if(t->data>t1->data)t1=t1->right;
	    else t1=t1->left;
	}
	return NULL;
    }
    void rightrotate(node *t)
    {
	if(t==NULL)return;
	node *q=getparent(t->data);
	int i,j=0;
	if(t==root)j++;
	if(q!=NULL && q->right==t){i=1;} else {i=0;}
	node *u=t->left;
	if(u==NULL)return;
	node *v=t->right;
	t->left=u->right;
	u->right=t;
	if(q==NULL){root=u;return;}
	if(i)q->right=u;
	else q->left=u;
    }
    void leftrotate(node *t)
    {
	if(t==NULL)return;
	node *q=getparent(t->data);
	int i,j=0;
	if(t==root)j++;
	if(q!=NULL && q->right==t){i=1;} else {i=0;}
	node *u=t->right;
	if(u==NULL)return;
	node *v=t->left;
	t->right=u->left;
	u->left=t;
	if(q==NULL){root=u;return;}
	if(i)q->right=u;
	else q->left=u;
    }
    node *getnode(int key)
    {
	node *t=root;
	while(true)
	{
	    if(t==NULL)return NULL;
	    if(t->data==key)return t;
	    if(key>t->data)t=t->right;
	    else t=t->left;
	}
	return NULL;
    }	    
    void inorder(node *t)
    {
	if(t==NULL)return;
	inorder(t->left);
	cout<<"  "<<t->data;
	inorder(t->right);
    }
    void preorder(node *t)
    {
	if(t==NULL)return;
	cout<<"  "<<t->data;
	preorder(t->left);
	preorder(t->right);
    }
    void postorder(node *t)
    {
	if(t==NULL)return;
	postorder(t->left);
	postorder(t->right);
	cout<<"  "<<t->data;
    }
};