C++ program to perform Insertion and Deletion operations on AVL-trees

/* Write a C++ program to perform the following operations on AVL-trees:
a) Insertion.
b) Deletion. */

#include<iostream>
#include<stdlib.h>
using namespace std;
#define TRUE 1
#define FALSE 0
#define NULL 0
class AVL;
class AVLNODE
{
	friend class AVL;
	private:
		int data;
		AVLNODE *left,*right;
		int bf;
};
class AVL
{
	private:
		AVLNODE *root;
	public:
		AVLNODE *loc,*par;
		AVL()
		{
			root=NULL;
		}
		int insert(int);
		void displayitem();
		void display(AVLNODE *);
		void removeitem(int);
		void remove1(AVLNODE *,AVLNODE *,int);
		void remove2(AVLNODE *,AVLNODE *,int);
		void search(int x);
		void search1(AVLNODE *,int);
};
int AVL::insert(int x)
{
	AVLNODE *a,*b,*c,*f,*p,*q,*y,*clchild,*crchild;
	int found,unbalanced;
	int d;
	if(!root)   //special case empty tree
	{          y=new AVLNODE;
		y->data=x;
		root=y;
		root->bf=0;
		root->left=root->right=NULL;
		return TRUE;	}
	//phase 1:locate insertion point for x.a keeps track of the most
	// recent node with balance factor +/-1,and f is the parent of a
	// q follows p through the tree.
	f=NULL;
	a=p=root;
	q=NULL;
	found=FALSE;
	while(p&&!found)
	{                 //search for insertion point for x
		if(p->bf)
		{
			a=p;
			f=q;
		}
		if(x<p->data)    //take left branch
		{
			q=p;
			p=p->left;
		}
		else if(x>p->data)
		{
			q=p;
			p=p->right;
		}
		else
		{
			y=p;
			found=TRUE;
		}
	}               //end while
	//phase 2:insert and rebalance.x is not in the tree and
	// may be inserted as the appropriate child of q.
	if(!found)
	{
		y = new AVLNODE;
		y->data=x;
		y->left=y->right=NULL;
		y->bf=0;
		if(x<q->data)    //insert as left child
		q->left=y;
		else
		q->right=y;    //insert as right child
		//adjust balance factors of nodes on path from a to q
		//note that by the definition of a,all nodes on this
		//path must have balance factors of 0 and so will change
		//to +/- d=+1 implies that x is inserted in the left
		// subtree of a d=-1 implies
		//to that x inserted in the right subtree of a.
 
 
if(x>a->data)
		{
			p=a->right;
			b=p;
			d=-1;
		}
		else
		{
			p=a->left;
			b=p;
			d=1;
		}
		while(p!=y)
		if(x>p->data)          //height of  right increases by 1
		{
			p->bf=-1;
			p=p->right;
		}
		else                 //height of left increases by 1
		{
			p->bf=1;
			p=p->left;
		}
		//is tree unbalanced
		unbalanced=TRUE;
		if(!(a->bf)||!(a->bf+d))
		{                   //tree still balanced
			a->bf+=d;
			unbalanced=FALSE;
		}
		if(unbalanced)   //tree unbalanced,determine rotation type
		{
			if(d==1)
			{         //left imbalance
				if(b->bf==1)      //rotation type LL
				{
					a->left=b->right;
					b->right=a;
					a->bf=0;
					b->bf=0;
				}
				else    //rotation type LR
				{
					c=b->right;
					b->right=c->left;
					a->left=c->right;
					c->left=b;
					c->right=a;
 
 
switch(c->bf)
					{
						case 1: a->bf=-1;  //LR(b)
							b->bf=0;
							break;
						case -1:b->bf=1;  //LR(c)
							a->bf=0;
							break;
						case 0: b->bf=0;  //LR(a)
							a->bf=0;
							break;
					}
					c->bf=0;
					b=c; //b is the new root
				} //end of LR
			}         //end of left imbalance
		      else    //right imbalance
		      {
				if(b->bf==-1)      //rotation type RR
				{
					a->right=b->left;
					b->left=a;
					a->bf=0;
					b->bf=0;
				}
				else    //rotation type LR
				{
					c=b->right;
					b->right=c->left;
					a->right=c->left;
					c->right=b;
					c->left=a;
					switch(c->bf)
					{
						case 1: a->bf=-1;  //LR(b)
							b->bf=0;
							break;
						case -1:b->bf=1;  //LR(c)
							a->bf=0;
							break;
						case 0: b->bf=0;  //LR(a)
							a->bf=0;
							break;
					}
					c->bf=0;
					b=c; //b is the new root
				} //end of LR
			   }
//subtree with root b has been rebalanced and is the new subtree
 
if(!f)
			root=b;
			else if(a==f->left)
			f->left=b;
			else if(a==f->right)
			f->right=b;
		}   //end of if unbalanced
		return TRUE;
	}         //end of if(!found)
	return FALSE;
}     //end of AVL INSERTION
 
void AVL::displayitem()
{
	display(root);
}
void AVL::display(AVLNODE *temp)
{
	if(temp==NULL)
	return;
	cout<<temp->data<<" ";
	display(temp->left);
	display(temp->right);
}
void AVL::removeitem(int x)
{
	search(x);
	if(loc==NULL)
	{
		cout<<"\nitem is not in tree";
		return;
	}
	if(loc->right!=NULL&&loc->left!=NULL)
	remove1(loc,par,x);
	else
	remove2(loc,par,x);
}
void AVL::remove1(AVLNODE *l,AVLNODE *p,int x)
{
	AVLNODE *ptr,*save,*suc,*psuc;
	ptr=l->right;
	save=l;
	while(ptr->left!=NULL)
	{
		save=ptr;
		ptr=ptr->left;
	}
	suc=ptr;
	psuc=save;
	remove2(suc,psuc,x);
	if(p!=NULL)
		if(l==p->left)
			p->left=suc;
		else
			p->right=suc;
	else
		root=l;
	 suc->left=l->left;
	 suc->right=l->right;
	  return;
}
void AVL::remove2(AVLNODE *s,AVLNODE *p,int x)
{
	AVLNODE *child;
	if(s->left==NULL && s->right==NULL)
		child=NULL;
	else if(s->left!=NULL)
		child=s->left;
	else
		child=s->right;
	if(p!=NULL)
		if(s==p->left)
			p->left=child;
		else
			p->right=child;
	else
		root=child;
 
}
void AVL::search(int x)
{
	search1(root,x);
}
void AVL::search1(AVLNODE *temp,int x)
{
       AVLNODE *ptr,*save;
       int flag;
       if(temp==NULL)
       {
		cout<<"\nthe tree is empty";
		return;
       }
       if(temp->data==x)
       {
		cout<<"\nthe item is root and is found";
		par=NULL;
		loc=temp;
		par->left=NULL;
		par->right=NULL;
		return;       }
       if( x < temp->data)
       {
		ptr=temp->left;
		save=temp;
       }
       else
       {
		ptr=temp->right;
		save=temp;
       }
       while(ptr!=NULL)
       {
		if(x==ptr->data)
		{       flag=1;
			cout<<"\nitemfound";
			loc=ptr;
			par=save;
 
		}
		if(x<ptr->data)
		ptr=ptr->left;
		else
		ptr=ptr->right;
       }
       if(flag!=1)
       {
		cout<<"item is not there in tree";
		loc=NULL;
		par=NULL;
		cout<<loc;
		cout<<par;
       }
}
 
main()
{
	AVL a;
	int x,y,c;
        char ch;	
	do
	{
		cout<<"\n1.insert";
		cout<<"\n2.display";
		cout<<"\n3.delete";
		cout<<"\n4.search";
		cout<<"\n5.exit";
		cout<<"\nEnter u r choice to perform on AVL tree";
		cin>>c;
 
 
switch(c)
		{
			case 1:cout<<"\nEnter an element to insert into tree";
				cin>>x;
				a.insert(x);
				break;
			case 2:a.displayitem(); break;
			case 3:cout<<"\nEnter an item to deletion";
			       cin>>y;
			       a.removeitem(y);
			       break;
			case 4:cout<<"\nEnter an element to search";
				cin>>c;
				a.search(c);
				break;
			case 5:exit(0);	break;
		      default :cout<<"\nInvalid option try again";
		}
		cout<<"\ndo u want to continue";
		cin>>ch;
	}
	while(ch=='y'||ch=='Y');
}

OUTPUT
1.insert 2.display 3.delete 4.search 5.exit
Enter u r choice to perform on AVL tree1
Enter an element to insert into tree4

do u want to continue

1.insert 2.display 3.delete 4.search 5.exit
Enter u r choice to perform on AVL tree1
Enter an element to insert into tree5

Start exploring endless computing possibilities with your own Raspberry Pi computer and accessories. Perfect for beginners and students.

do u want to continue

1.insert 2.display 3.delete 4.search 5.exit
Enter u r choice to perform on AVL tree3

Enter an item to deletion5

itemfound
do u want to continue

1.insert 2.display 3.delete 4.search 5.exit
Enter u r choice to perform on AVL tree2
4
do u want to continue 4


10 Responses to “C++ program to perform Insertion and Deletion operations on AVL-trees”

  1. insertion is not working .
    it only inserts 2 elements and after that shows segmentation fault.

    Reply
  2. I did the following insertions
    1,5,6,2,3,4

    then deleted 1

    and then ask to display the tree.
    I got 3 2 1

    This is not complete code.

    Reply
  3. Omair The Programmer

    This is too difficult to understand on a beginner level. Please explain each and every step thoroughly Ranjith. Nice effort though.

    Reply
  4. I simply want to meinton I’m very new to weblog and seriously enjoyed your web-site. Almost certainly I’m want to bookmark your website . You absolutely come with excellent stories. Thanks for sharing with us your webpage.

    Reply
  5. Алексей

    Ну и реализация просто бешеная, без обид честное слово.

    Reply
  6. usman khan

    plz give me a parogram in c++ queue insartion and deletion just

    Reply

Leave a Reply