AVL Tree implementation in C++

AVLTree.cpp

#include <iostream>

using namespace std;

struct Node{
	int val;
	Node* left;
	Node* right;
	int ht;
};

class AVLTree{

public:
	Node* root=NULL;

	int height(Node* curnode){
		if((curnode)==NULL){
			return 0;
		}
		return (max(height((curnode)->left),height((curnode)->right))+1);
	}

	void _insert(Node** curnode, int key){

	    if(key<(*curnode)->val){
	        if((*curnode)->left==NULL){
	            Node* temp=new Node;
	            temp->val=key;
	            temp->left=NULL;
	            temp->right=NULL;
	            temp->ht=0;
	            (*curnode)->left=temp;
	        }
	        else
	        	_insert(&((*curnode)->left),key);
	    }

	    else if(key>(*curnode)->val){
	        if((*curnode)->right==NULL){
	            Node* temp=new Node;
	            temp->val=key;
	            temp->left=NULL;
	            temp->right=NULL;
	            temp->ht=0;
	            (*curnode)->right=temp;
	        }
	        else
		        _insert(&((*curnode)->right),key);
    	}

    	balanceTree(curnode);

	}

	void insert(int key){
	    if(root==NULL){
	        Node* temp=new Node;
	        temp->val=key;
	        temp->left=NULL;
	        temp->right=NULL;
	        temp->ht=0;
	        root=temp;
	        return;
	    }
	    _insert(&root,key);
	}

	void balanceTree(Node** curnode){

		if((*curnode)==NULL){
			return;
		}

		int bfactor,l,r;
	    
	    if((*curnode)->left==NULL){
	        l=-1;
	    }
	    else{
	        l=(*curnode)->left->ht;
	    }
	    
	    if((*curnode)->right==NULL){
	        r=-1;
	    }
	    else{
	        r=(*curnode)->right->ht;
	    }
	    
	    (*curnode)->ht=max(l,r)+1;
	    
	    bfactor=l-r;
	    
	    if(bfactor==-2){
	        if((*curnode)->right->left==NULL){
	            l=-1;
	        }
	        else{
	            l=(*curnode)->right->left->ht;
	        }

	        if((*curnode)->right->right==NULL){
	            r=-1;
	        }
	        else{
	            r=(*curnode)->right->right->ht;
	        }
	        bfactor=l-r;
	        
	        if(bfactor!=1){
	            (*curnode)->ht-=2;
	            Node* temp=(*curnode)->right;
	            (*curnode)->right=temp->left;
	            temp->left=(*curnode);
	            *curnode=temp;
	            if((*curnode)->left!=NULL){
	                l=(*curnode)->left->ht;
	            }
	            else{
	                l=-1;
	            }
	            if((*curnode)->right!=NULL){
	                r=(*curnode)->right->ht;
	            }
	            else{
	                r=-1;
	            }
	            (*curnode)->ht=max(l,r)+1;
	            return;
	        }
	        else{
	            Node** act=&(*curnode)->right;
	            (*act)->ht-=1;
	            Node* temp=(*act)->left;
	            temp->ht+=1;
	            (*act)->left=temp->right;
	            temp->right=(*act);
	            *act=temp;
	            Node* temp2=(*curnode)->right;
	            (*curnode)->ht-=2;
	            (*curnode)->right=temp2->left;
	            temp2->left=(*curnode);
	            *curnode=temp2;
	            if((*curnode)->left!=NULL){
	                l=(*curnode)->left->ht;
	            }
	            else{
	                l=-1;
	            }
	            if((*curnode)->right!=NULL){
	                r=(*curnode)->right->ht;
	            }
	            else{
	                r=-1;
	            }
	            (*curnode)->ht=max(l,r)+1;
	            return;
	        }
	    }

	    if(bfactor==2){
	        if((*curnode)->left->left==NULL){
	            l=-1;
	        }
	        else{
	            l=(*curnode)->left->left->ht;
	        }

	        if((*curnode)->left->right==NULL){
	            r=-1;
	        }
	        else{
	            r=(*curnode)->left->right->ht;
	        }
	        bfactor=l-r;
	        if(bfactor!=-1){
	            (*curnode)->ht-=2;
	            Node* temp=(*curnode)->left;
	            (*curnode)->left=temp->right;
	            temp->ht+=1;
	            temp->right=(*curnode);
	            *curnode=temp;
	            if((*curnode)->left!=NULL){
	                l=(*curnode)->left->ht;
	            }
	            else{
	                l=-1;
	            }
	            if((*curnode)->right!=NULL){
	                r=(*curnode)->right->ht;
	            }
	            else{
	                r=-1;
	            }
	            (*curnode)->ht=max(l,r)+1;
	            return;
	        }
	        else{
	            Node** act=&(*curnode)->left;
	            (*act)->ht-=1;
	            Node* temp=(*act)->right;
	            temp->ht+=1;
	            (*act)->right=temp->left;
	            temp->left=(*act);
	            *act=temp;
	            Node* temp2=(*curnode)->left;
	            (*curnode)->ht-=2;
	            (*curnode)->left=temp2->right;
	            temp2->right=(*curnode);
	            *curnode=temp2;
	            if((*curnode)->left!=NULL){
	                l=(*curnode)->left->ht;
	            }
	            else{
	                l=-1;
	            }
	            if((*curnode)->right!=NULL){
	                r=(*curnode)->right->ht;
	            }
	            else{
	                r=-1;
	            }
	            (*curnode)->ht=max(l,r)+1;
	            return;
	        }
	    }

	}

	void predecessorDelete(Node** actual, Node** curnode){

		_predecessorDelete(actual,&((*curnode)->left));
		balanceTree(curnode);

	}

	void _predecessorDelete(Node** actual, Node** curnode){

		if((*curnode)->right!=NULL){
			_predecessorDelete(actual,&((*curnode)->right));
		}

		else{
			(*actual)->val=(*curnode)->val;
			*curnode=(*curnode)->left;
			return;
		}

		balanceTree(curnode);

	}

	void successorDelete(Node** actual, Node** curnode){

		_successorDelete(actual,&((*curnode)->right));
		balanceTree(curnode);

	}

	void _successorDelete(Node** actual, Node** curnode){

		if((*curnode)->left!=NULL){
			_successorDelete(actual,&((*curnode)->left));
		}

		else{
			(*actual)->val=(*curnode)->val;
			*curnode=(*curnode)->right;
			return;
		}

		balanceTree(curnode);

	}

	void _deleteNode(Node** curnode, int key){

		if((*curnode)==NULL){
			return;
		}

		if(key<(*curnode)->val){
			_deleteNode(&((*curnode)->left),key);
		}
		else if(key>(*curnode)->val){
			_deleteNode(&((*curnode)->right),key);
		}
		else{
			if((*curnode)->left==NULL && (*curnode)->right==NULL){
				*curnode=NULL;
				return;
			}
			else if((*curnode)->left!=NULL){
				predecessorDelete(curnode,curnode);
			}
			else{
				successorDelete(curnode,curnode);
			}
		}

		balanceTree(curnode);

	}

	void deleteNode(int key){

		if(root==NULL){
			return;
		}
		_deleteNode(&root, key);

	}

	void levelorder(){

		if(root==NULL){
			return;
		}
		for(int i=0;i<height(root);i++){
			_levelorder(root,i,i);
		}

	}

	void _levelorder(Node* curnode, int i, int j){

		if(curnode==NULL){
			cout<<"level: "<<j<<" NULL"<<endl;
			return;
		}

		if(i==0){
			cout<<"level: "<<j<<" "<<curnode->val<<endl;
			return;
		}

		_levelorder(curnode->left,i-1,j);
		_levelorder(curnode->right,i-1,j);

	}

};

int main(){

	AVLTree avl;
	// single rotate -2,-1
	avl.insert(20);
	avl.insert(10);
	avl.insert(28);
	avl.insert(32);
	avl.insert(5);
	avl.insert(30);
	avl.insert(34);
	avl.insert(29);

	// single rotate 2,1 
	// avl.insert(40);
	// avl.insert(30);
	// avl.insert(50);
	// avl.insert(35);
	// avl.insert(20);
	// avl.insert(10);
	// avl.insert(25);

	// double rotate -2,1
	// avl.insert(20);
	// avl.insert(10);
	// avl.insert(15);
	// avl.insert(28);
	// avl.insert(5);
	// avl.insert(25);
	// avl.insert(32);
	// avl.insert(4);
	// avl.insert(30);
	// avl.insert(34);
	// avl.insert(29);
	// avl.insert(31);

	avl.deleteNode(30);

	avl.levelorder();

	avl.inorder();

}