/** C++ program to Implement AVL Tree*/#include<iostream>#include<cstdio>#include<sstream>#include<algorithm>#define pow2(n) (1 << (n))using namespace std;
/** Node Declaration*/struct avl_node{int data;
struct avl_node *left;
struct avl_node *right;
}*root;
/** Class Declaration*/class avlTree{public:
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 );
void display(avl_node *, int);
void inorder(avl_node *);
void preorder(avl_node *);
void postorder(avl_node *);
avlTree()
{root = NULL;
}};
/** Main Contains Menu*/int main()
{int choice, item;
avlTree avl;while (1)
{cout<<"\n---------------------"<<endl;
cout<<"AVL Tree Implementation"<<endl;
cout<<"\n---------------------"<<endl;
cout<<"1.Insert Element into the tree"<<endl;
cout<<"2.Display Balanced AVL Tree"<<endl;
cout<<"3.InOrder traversal"<<endl;
cout<<"4.PreOrder traversal"<<endl;
cout<<"5.PostOrder traversal"<<endl;
cout<<"6.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>choice;
switch(choice)
{case 1:
cout<<"Enter value to be inserted: ";
cin>>item;
root = avl.insert(root, item);
break;
case 2:
if (root == NULL)
{cout<<"Tree is Empty"<<endl;
continue;
}cout<<"Balanced AVL Tree:"<<endl;
avl.display(root, 1);
break;
case 3:
cout<<"Inorder Traversal:"<<endl;
avl.inorder(root);
cout<<endl;
break;
case 4:
cout<<"Preorder Traversal:"<<endl;
avl.preorder(root);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal:"<<endl;
avl.postorder(root);
cout<<endl;
break;
case 6:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}}return 0;
}/** Height of AVL Tree*/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;
}/** Height Difference*/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;
}/** Right- Right Rotation*/avl_node *avlTree::rr_rotation(avl_node *parent)
{avl_node *temp;
temp = parent->right;
parent->right = temp->left;
temp->left = parent;
return temp;
}/** Left- Left Rotation*/avl_node *avlTree::ll_rotation(avl_node *parent)
{avl_node *temp;
temp = parent->left;
parent->left = temp->right;
temp->right = parent;
return temp;
}/** Left - Right Rotation*/avl_node *avlTree::lr_rotation(avl_node *parent)
{avl_node *temp;
temp = parent->left;
parent->left = rr_rotation (temp);
return ll_rotation (parent);
}/** Right- Left Rotation*/avl_node *avlTree::rl_rotation(avl_node *parent)
{avl_node *temp;
temp = parent->right;
parent->right = ll_rotation (temp);
return rr_rotation (parent);
}/** Balancing AVL Tree*/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);
elsetemp = lr_rotation (temp);
}else if (bal_factor < -1)
{if (diff (temp->right) > 0)
temp = rl_rotation (temp);
elsetemp = rr_rotation (temp);
}return temp;
}/** Insert Element into the tree*/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);
}return root;
}/** Display AVL Tree*/void avlTree::display(avl_node *ptr, int level)
{int i;
if (ptr!=NULL)
{display(ptr->right, level + 1);
printf("\n");
if (ptr == root)
cout<<"Root -> ";
for (i = 0; i < level && ptr != root; i++)
cout<<" ";
cout<<ptr->data;
display(ptr->left, level + 1);
}}/** Inorder Traversal of AVL Tree*/void avlTree::inorder(avl_node *tree)
{if (tree == NULL)
return;
inorder (tree->left);
cout<<tree->data<<" ";
inorder (tree->right);
}/** Preorder Traversal of AVL Tree*/void avlTree::preorder(avl_node *tree)
{if (tree == NULL)
return;
cout<<tree->data<<" ";
preorder (tree->left);
preorder (tree->right);
}/** Postorder Traversal of AVL Tree*/void avlTree::postorder(avl_node *tree)
{if (tree == NULL)
return;
postorder ( tree ->left );
postorder ( tree ->right );
cout<<tree->data<<" ";
}
$ g++ avl_tree.cpp $ a.out --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Tree is Empty --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 8 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: Root -> 8 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 5 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: Root -> 8 5 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 4 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 8 Root -> 5 4 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 11 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 11 8 Root -> 5 4 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 15 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 15 11 8 Root -> 5 4 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 3 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 15 11 8 Root -> 5 4 3 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 6 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 15 11 8 6 Root -> 5 4 3 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 2 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 15 11 8 6 Root -> 5 4 3 2 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 4 Preorder Traversal: 5 3 2 4 11 8 6 15 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 5 Postorder Traversal: 2 4 3 6 8 15 11 5 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 3 Inorder Traversal: 2 3 4 5 6 8 11 15 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 15 11 8 6 Root -> 5 4 3 2 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 6 ------------------ (program exited with code: 1) Press return to continue
Link of this program http://www.sanfoundry.com/
