Answer to Question #271365 in C++ for Myname

Question

Write a program to implement an AVL Tree having following functionalities.

 Insert (): This function inserts a new node to an AVL tree. The node contains an integer type of data.

 BF(): This function returns the balance factor of a given node.

 LL(): This function performs LL rotation.

 RR(): This function performs RR rotation.

 LR(): This function performs LR rotation.

 RL(): This function performs RL rotation.

 Display (): This function displays inorder traversal sequence of the AVL tree.

After inserting a new node, if the resulting tree is not AVL then insert function calls appropriated rotation function

to make the tree an AV

Answer 1

#include<iostream>
#include<algorithm>
using namespace std;

struct Node
{
	int data;
	Node* left;
	Node* right;
	int height;
	Node(int _data):data(_data), left(NULL),right(NULL),height(1){}
};

class AVLTree
{
public:
	int getHeight(Node* p)
	{
		if(p==NULL)
			return 0;
		else
			return p->height;
		
	}
	int BF(Node* p)
	{
		if(p==NULL)
			return 0;
		else
			return getHeight(p->left)-getHeight(p->right);
	}
	Node* Insert(Node* p, int value)
	{
		//Usual BST insertion
		if(p==NULL)
			return new Node(value);
		if(value<p->data)
			p->left=Insert(p->left, value);
		else if(value>p->data)
			p->right=Insert(p->right,value);
		else 
			return p;//discard equal value
		//Find height
		p->height=1+max(getHeight(p->left),getHeight(p->right));
		//Find balance coefficient
		int bal=BF(p);
		//case RR
		if(bal<-1&&value>p->right->data)
			return LL(p);
		//case LL
		if(bal>1&&value<p->left->data)
			return RR(p);
		//case LR
		if(bal>1&&value>p->left->data)
			return LR(p);
		//case RL
		if(bal<-1&&value<p->right->data)
			return RL(p);
			
		return p;
	}
	
	Node* RR(Node* p)
	{
		Node* l=p->left;
		Node* r=l->right;
		//Rotation
		l->right=p;
		p->left=r;
		//Fing heights
		p->height=1+max(getHeight(p->left),getHeight(p->right));
		l->height=1+max(getHeight(l->left),getHeight(l->right));
		return l;
		
	}
	Node* LL(Node* p)
	{
		Node* r=p->right;
		Node* l=r->left;
		//Rotation
		r->left=p;
		p->right=l;
		//Fing heights
		p->height=1+max(getHeight(p->left),getHeight(p->right));
		r->height=1+max(getHeight(r->left),getHeight(r->right));
		return r;
	}
	Node* LR(Node* p)
	{
		p->left=LL(p->left);
		return RR(p);
	}
	Node* RL(Node* p)
	{
		p->right=RR(p->right);
		return LL(p);
	}
	void Display(Node* p)
	{
		if(p==NULL)
			return;
		Display(p->left);
		cout<<p->data<<" ";
		Display(p->right);
	}
};

int main()
{
	AVLTree a;
	Node* root=NULL;
	root=a.Insert(root,7);
	root=a.Insert(root,4);
	root=a.Insert(root,8);
	root=a.Insert(root,2);
	root=a.Insert(root,3);
	root=a.Insert(root,9);
	root=a.Insert(root,6);
	root=a.Insert(root,1);
	root=a.Insert(root,5);
	a.Display(root);
}