AVL Tree Implementation using C++.

avl.cpp

/*
    Implementing AVL Tree using C++.
    Ajinkya Sonawane [AJ-CODE-7]
*/

#include<iostream>
using namespace std;

class node
{
	int data,bf;            //data and balance factor field
    	node *left,*right;      //left and right pointer of a node
    	friend class avl;       //allow class avl to access private elements of class node
};

class avl
{
    	node *root,*temp;
	public:
        	avl();  //Constructor for initialization
        	void create(int );          //method to create an avl tree
        	node* insert(node*,node*);  //method to insert elements in the avl tree
        	void display(node*);        //method to display the elements in Inorder
        	node* delNode(node*,int);   //method to delete a particular value from the tree

        	int height(node*);          //method to calculate height of a particular node
        	int bal(node*);             //method to calculate the balance factor used for balancing the avl
        	node* findMin(node*);       //method to find the node with minimum value
        	void put(node*);            //method to put the balance factors to the field of every node

	        node* balance(node*);       //method to balance the avl
	        node* leftRotate(node*);    //method to rotate nodes in left direction
	        node* rightRotate(node*);   //method to rotate nodes in right direction

	        void choose();              //method for menu driven options to be performed on avl tree
	        ~avl(); //Destructor for deallocating the used memory
};

avl :: avl()
{
	    root = NULL;        //initializing root to NULL
	    temp = NULL;        //initializing temp to NULL
}
void avl :: create(int total)
{
	    int val;    //variable to accept element

	    for(int i=0;i<total;i++)
	    {
	        cout<<"\nEnter the element : ";
	        cin>>val;
	
	        temp = new node;
	        temp->left = NULL;
	        temp->right = NULL;
	        temp->data = val;
	        root = insert(root,temp);   //insert function will return the root of the balanced tree
	
	    }
}
	
node* avl :: insert(node* r,node* t)
{
	    if(r == NULL)
	        return t;
	    else if(t->data < r->data)          //If element to be inserted is smaller than the root then insert to the left
	    {
	        r->left = insert(r->left,t);
	        r = balance(r);
	    }
	    else                                //else insert to the right
	    {
	        r->right = insert(r->right,t);
	        r = balance(r);
	    }
	
	    return r;      //return r(node) of every call to the previous call
}

void avl :: put(node* r)
{
	    if(r == NULL)
	        return;
	    r->bf = bal(r);     //putting balance factor to the node
	    put(r->left);       //traversing left subtree
	    put(r->right);      //traversing right subtree
	}
	
void avl :: display(node* r)
{
	    if(r == NULL)
	        return;
	    else
	    {
	        display(r->left);
	        cout<<r->data<<"\t\t"<<r->bf<<"\n";
	        display(r->right);
	    }
}

int avl :: height(node *r)
{
	    //Here height is the number of nodes present in the longest path  (including root) and not the number of edges
	    if(r == NULL)
	        return 0;
	    else
	    {
	        int lheight = height(r->left)+1;
	        int rheight = height(r->right)+1;
	
	        return (lheight > rheight) ? lheight : rheight; //returning longest path from root
	    }
}

int avl :: bal(node *r)
{
	    int left = height(r->left);
	    int right = height(r->right);
	
	    return (left-right);    //returning difference between left subtree and right subtree
}



node* avl :: leftRotate(node* r)
{
	    //rotating in left direction
	    node* cur = r->left;
	    r->left = cur->right;
	    cur->right = r;
	
	    return cur;
}

node* avl :: rightRotate(node* r)
{
	    //rotating in right direction
	    node* cur = r->right;
	    r->right = cur->left;
	    cur->left = r;
	
	    return cur;
}

node* avl :: balance(node* r)
{
	    int bf = bal(r);
	    if (bf > 1)
	    {
	        if (bal(r->left) > 0)
	        {
	            //simple rotation on the left of left subtree
	            r = leftRotate(r);
	        }
	        else
	        {
	            //complex rotation on right of left subtree
	            r->left = rightRotate(r->left);
	            return leftRotate(r);
	        }
	    }
	    else if (bf < -1)
	    {
	        if (bal(r->right) > 0)
	        {
	            //complex rotation on left of right subtree
	            r->right = leftRotate(r->right);
	            return rightRotate(r);
	        }
	        else
	        {
	            //simple rotation on right of right subtree
	            r = rightRotate(r);
	        }
	    }
	    return r;
}

node* avl :: delNode(node* r,int x)
{
	node *temp;
	if(r == NULL)
		return r;
	else if(x < r->data)
	{
		r->left = delNode(r->left,x);
	}
	else if(x > r->data)
	{
		r->right = delNode(r->right,x);
	}
	else
	{
		if(r->left == NULL)
		{
			temp = r->right;
			delete r;
			return temp;
		}
		else if(r->right == NULL)
		{
			temp = r->left;
			delete r;
			return temp;
		}
		else
		{
			temp = findMin(r->right);
			r->data = temp->data;
			r->right = delNode(r->right,temp->data);    //deleting the node from the tree
			r = balance(r);                             //balancing the tree after deletion
		}
	}
	return r;
}

node* avl :: findMin(node* r)
{
	node* cur = r;
	while(cur->left != NULL)
		cur = cur->left;
	return cur; //returning node with the minimum value from the given node r
}

void avl :: choose()
{
    //Menu for performing operations on AVL	
	int ch,total;

    	do
    	{
        	cout<<"\n\t\t | AVL Tree |\n";
        	cout<<"\n1.Create AVL Tree";
        	cout<<"\n2.Insert Element";
        	cout<<"\n3.Find Height";
        	cout<<"\n4.Display InOrder";
        	cout<<"\n5.Delete Element";
        	cout<<"\n6.Exit";
        	cout<<"\n>>";
        	cin>>ch;
	
        	switch(ch)
        	{
        	    case 1:
        	        cout<<"\nEnter the number of elements you want to enter : ";
        	        cin>>total;
        	        create(total);
        	        break;
        	    case 2:
        	        create(1);
        	        break;
        	    case 3:
        	        cout<<"\nHeight of the tree : "<<height(root)<<"\n";
        	        break;
        	    case 4:
        	        cout<<"\n\t| The AVL Tree |\n\n";
        	        if(root == NULL)
        	        {
        	            cout<<"\n***** No Tree Present ******\n";
        	            break;
        	        }
        	        cout<<"\nNodes\tBalance Factor\n";
        	        put(root);
        	        display(root);
        	        cout<<endl;
        	        break;
        	    case 5:
        	        cout<<"\nEnter the element to be deleted : ";
        	        int x;
        	        cin>>x;
        	        if(root == NULL)
        	        {
        	            cout<<"\n***** No Tree Present ******\n";
        	            break;
        	        }
        	        root = delNode(root,x);
        	        cout<<"\n***** Element Deleted Successfully ******\n";
        	        break;
        	    case 6:
        	        cout<<"\n****** EXIT *******\n";
        	        break;
        	    default:
        	        cout<<"\nInvalid Choice\n";
        	        break;
        	}
    	}while(ch != 6);
    	return;
}

avl :: ~avl()
{
    	delete root;
    	delete temp;
}
int main()
{
    	avl a;
    	a.choose();
    	return 0;
}

Good work