AVL Tree

AVLTree.cpp

#include <iostream>
using namespace std;
class Node{
	public:
		int data;
		Node* left;
		Node* right;
		int height;
		Node(int data){
			this->data=data;
			this->left=NULL;
			this->right=NULL;
			this->height=0;
		}
};

class BinaryTree{
	public:
		Node* RightRotate(Node* x){
			Node* y=x->left;
			Node* yRight=y->right;
			y->right=x;
			x->left=yRight;
			y->height=Height(y);
			x->height=Height(x);
			return y;


		}

		Node* LeftRotate(Node* x){
			Node* y=x->right;
			Node* yLeft=y->left;

			y->left=x;
			x->right=yLeft;
			y->height=Height(y);
			x->height=Height(x);
			return y;



		}
		int GetBalance(Node* r){
			if(r==NULL){
				return 0;
			}
			return Height(r->left)-Height(r->right);
		}

		// for each node entry, find its height
		Node* Insert(int data, Node* root){
			if(root==NULL){
				root=new Node(data);
				return root;

			}else if(data<root->data){
				root->left=Insert(data, root->left);

			}else{
				root->right=Insert(data, root->right);

			}
			root->height=Height(root);
			int balance=GetBalance(root);

			//left-left case, then right rotate
			if(balance>1 && data<root->left->data){
				return RightRotate(root);
			}

			//right-right
			if(balance<-1 && data>root->right->data){
				return LeftRotate(root);
			}

			// left-right, then left rotation then right rotation
			if(balance>1 && data<root->left->data){
                root->left=LeftRotate(root);
                return  RightRotate(root);
			}

			//right-left, then right rotation then left rotation
			if(balance<-1 && data<root->right->data){
				root->right=RightRotate(root->right);
				return LeftRotate(root);
			}
			return root;

		}

		void Print(Node* root){
			if(root==NULL){
				return;
			}
			cout << root->data << endl;
			Print(root->left);

			Print(root->right);
		}

		int Height(Node* root){
			if(root==NULL){
				return -1;
			}
			int l=Height(root->left);
			int r=Height(root->right);

			return(max(l, r)+1);
		}
};
int main(){

	Node* root=NULL;
	BinaryTree* bt;
	root=bt->Insert(10, root);
	root=bt->Insert(18, root);
	root=bt->Insert(37, root);
	root=bt->Insert(50, root);
	root=bt->Insert(79, root);
	bt->Print(root);



	return 0;
}