What is the AVL tree?
AVL tree is a self-balancing Binary Search Tree (BST) where the
difference between heights of left and right subtrees cannot be more
then one for all nodes. An Example Tree is an AVL Tree.
C++ Example Of AVL Tree ....
#include<iostream>
using namespace::std;
class avl_node{
public:
int data;
avl_node* left;
avl_node* right;
avl_node(){
data=0;
left=NULL;
right=NULL;
}
void setData(int a)
{
this->data=a;
}
int getData()
{
return data;
}
void setLeft(avl_node* nextPointer)
{
this->left=nextPointer;
}
avl_node* getLeft()
{
return left;
}
void setRight(avl_node* nextPointer)
{
this->right=nextPointer;
}
avl_node* getRight()
{
return right;
}
bool isLeaf(int value)
{
if(this->left==NULL&&this->right==NULL)
{
return true;
}
else{
return false;
}
}
};
class avlTree{
public:
avl_node *root;
int height(avl_node*);
int diff(avl_node*);
avl_node *rr_rotation(avl_node*);
avl_node *ll_rotation(avl_node*);
avl_node *lr_rotation(avl_node*);
avl_node *rl_rotation(avl_node*);
avl_node * balance(avl_node*);
avl_node* insert(avl_node*,int);
avl_node* getSuccessor(avl_node*);
deleteNode(int);
void inorder(avl_node*);
void postorder(avl_node*);
void preorder(avl_node*);
avlTree()
{
root=NULL;
}
};
int avlTree::height(avl_node *temp)
{
int h=0;
if(temp!=NULL)
{
int l_height=height(temp->left);
int r_height=height(temp->right);
int max_height=max(l_height,r_height);
h=max_height+1;
}
return h;
}
int avlTree::diff(avl_node * temp)
{
int l_height=height(temp->left);
int r_height=height(temp->right);
int b_factor=l_height-r_height;
return b_factor;
}
avl_node* avlTree::ll_rotation(avl_node * parent)
{
avl_node* temp;
temp=parent->left;
parent->left=temp->right;
temp->right=parent;
return temp;
}
avl_node* avlTree::rr_rotation(avl_node * parent)
{
avl_node* temp;
temp=parent->right;
parent->right=temp->left;
temp->left=parent;
return temp;
}
avl_node *avlTree::lr_rotation(avl_node *parent)
{
avl_node *temp;
temp=parent->left;
parent->left=rr_rotation(temp);
return ll_rotation(parent);
}
avl_node* avlTree::rl_rotation(avl_node *parent)
{
avl_node* temp;
temp=parent->right;
parent->right=ll_rotation(temp);
return rr_rotation(parent);
}
avl_node* avlTree::balance(avl_node *temp)
{
int bal_factor=diff(temp);
if(bal_factor>1)
{
if(diff(temp->left)>0)
temp=ll_rotation(temp);
else
temp=lr_rotation(temp);
}
else if(bal_factor<-1)
{
if(diff(temp->right)>0)
temp=rl_rotation(temp);
else
temp=rr_rotation(temp);
}
return temp;
}
avl_node* avlTree::insert(avl_node *root,int value)
{
if(root==NULL)
{
root=new avl_node;
root->data=value;
root->left=NULL;
root->right=NULL;
return root;
}
else if(value<root->data)
{
root->left=insert(root->left,value);
root=balance(root);
}
else if(value>=root->data)
{
root->right=insert(root->right,value);
root=balance(root);
}
}
void avlTree::inorder(avl_node *tree)
{
if(tree==NULL)
return;
inorder(tree->left);
cout<<" "<<tree->data;
inorder(tree->right);
}
void avlTree::postorder(avl_node *tree)
{
if(tree==NULL)
return;
inorder(tree->left);
inorder(tree->right);
cout<<" "<<tree->data;
}
void avlTree::preorder(avl_node *tree)
{
if(tree==NULL)
return;
cout<<" "<<tree->data;
inorder(tree->left);
inorder(tree->right);
}
avlTree::deleteNode(int r)
{
avl_node* curr=root;
avl_node* currP;
bool goLeft=false;
while(curr!=NULL)
{
if(curr->data==r){
break;
}
else if(curr->data>r)
{
currP=curr;
curr=curr->left;
goLeft=true;
}
else if(curr->data<r)
{
currP=curr;
curr=curr->right;
goLeft=false;
}
}
if(curr==NULL)
{
cout<<"Node Not Found !"<<endl;
return 0;
}
if(curr->left==NULL&&curr->right==NULL)
{
cout<<"Case 1 ."<<endl;
cout<<endl<<"Node With Value "<<r<<" Deleted !"<<endl;
currP->left=currP->right=NULL;
delete curr;
root=balance(root);
}
else if(curr->right==NULL&&curr->left!=NULL)
{
cout<<"Case 2 ."<<endl;
cout<<endl<<"Node With Value "<<r<<" Deleted !"<<endl;
if(!goLeft)
currP->right=curr->left;
else
currP->left=curr->left;
curr->left=NULL;
delete curr;
root=balance(root);
}
else if(curr->right!=NULL&&curr->left==NULL)
{
cout<<"Case 3 ."<<endl;
cout<<endl<<"Node With Value "<<r<<" Deleted !"<<endl;
if(goLeft)
currP->left=curr->right;
else
currP->left=curr->right;
curr->right=NULL;
delete curr;
root=balance(root);
}
else {
cout<<"Case 4 ."<<endl;
cout<<endl<<"Node With Value "<<r<<" Deleted !"<<endl;
avl_node* successor = getSuccessor(curr);
if(curr == root){
root = successor;
}
if(goLeft){
currP->left = successor;
}else{
currP->right = successor;
}
successor->left= curr->left;
delete curr;
root=balance(root);
}
}
avl_node* avlTree::getSuccessor(avl_node *delNode){
avl_node* successorP = delNode;
avl_node* curr = delNode->right;
avl_node* successor = curr;
while(curr->left != NULL){
successorP = curr;
curr = curr->left;
successor = curr;
}
if(successor != delNode->right){
successorP->left = successor->right;
successor->right = delNode->right;
}
return successor;
}
int main()
{
int choice,item;
avlTree avl;
while(1)
{
cout<<"\n-----------------------"<<endl;
cout<<"AVL Tree Implementation|"<<endl;
cout<<"-----------------------"<<endl;
cout<<"1. Insert Element Into The Tree "<<endl;
cout<<"2. Inorder Traversal"<<endl;
cout<<"3. Preorder Traversal "<<endl;
cout<<"4. Postorder Traversal"<<endl;
cout<<"5. Display Root "<<endl;
cout<<"6. Delete Node "<<endl;
cout<<"7. Exit"<<endl;
cout<<"Enter Your Choice :";
cin>>choice;
switch(choice)
{
case 1:
cout<<endl<<"Enter Value To Be Inserted : ";
cin>>item;
avl.root=avl.insert(avl.root,item);
break;
case 2:
cout<<endl<<"Inorder Traversal :"<<endl;
avl.inorder(avl.root);
cout<<endl;
break;
case 3:
cout<<endl<<"Preorder Traversal :"<<endl;
avl.preorder(avl.root);
cout<<endl;
break;
case 4:
cout<<endl<<"PostOrder Traversal :"<<endl;
avl.postorder(avl.root);
cout<<endl;
break;
case 5:
cout<<endl<<"Displaying Root : "<<avl.root->data;
break;
case 6:
int r;
cout<<endl<<"Enter Id Of Node To Delete : ";
cin>>r;
avl.deleteNode(r);
break;
case 7:
break;
default:
cout<<endl<<"Wrong Choice "<<endl;
}
}
return 0;
}
No comments:
Post a Comment