#include<stdio.h>
#include<iostream>
#include<string.h>
#include<unistd.h>
using namespace std;
class avl
{
private:
struct anode
{
int key;
anode* left;
anode* right;
int height;
}*root;
public:
avl();
void insert(anode * &root,int key);
void insertintotree(int key);
void search(anode * root,int key);
void searchintree(int key);
void remove(anode * &root,int key);
void removekeyfromtree(int key);
int find_min(anode* root);
void preorderoftree();
void preorder(anode * root);
int height(anode *root);
int getbal(anode * root);
void rotatewithleftchild(anode *&key);
void doublewithleftchild(anode *&key);
void rotatewithrightchild(anode *&key);
void doublewithrightchild(anode*&key);
int max(int a,int b);
~avl();
};
avl::avl()
{
root=NULL;
}
int avl::max(int a,int b)
{return (a>=b)? a : b;
}
int avl::height(anode * root)
{
return root==NULL ? -1 : root->height;
}
void avl::insert(anode *&root,int key)
{
if(root==NULL)
{
root=new anode;
root->key=key;
root->left=NULL;
root->right=NULL;
root->height=0;
cout<<"\n Inserted \n";
return;
}
else if(key<root->key)
{
insert(root->left,key);
if(height(root->left)-height(root->right)==2)
if(key<root->left->key)
rotatewithleftchild(root);
else
doublewithleftchild(root);
}
else if(key>root->key)
{
insert(root->right,key);
if(height(root->right)-height(root->left)==2)
{if(key>root->right->key)
rotatewithrightchild(root);
else
doublewithrightchild(root);
}
}
root->height=1+max(height(root->left),height(root->right));
}
void avl::insertintotree(int key)
{
insert(root,key);
}
void avl::rotatewithleftchild(anode *&root)
{
anode * t=root->left;
root->left=t->left;
t->right=root;
root->height=1+max(height(root->left),height(root->right));
t->height=1+max(height(t->left),height(t->right));
root=t;
}
void avl::rotatewithrightchild(anode *&root)
{
anode * t=root->right;
root->right=t->left;
t->left=root;
root->height=1+max(height(root->left),height(root->right));
t->height=1+max(height(t->left),height(t->right));
root=t;
}
void avl::doublewithleftchild(anode* &root)
{
rotatewithrightchild(root->left);
rotatewithleftchild(root);
}
void avl::doublewithrightchild(anode* &root)
{
rotatewithleftchild(root->right);
rotatewithrightchild(root);
}
void avl::preorder(anode *root)
{
if(root==NULL)
return;
cout<<" - "<<root->key;
preorder(root->left);
preorder(root->right);
}
void avl::search(anode * root,int key)
{
if(root==NULL)
return ;
if(key<root->key)
search(root->left,key);
if(key>root->key)
search(root->right,key);
else if(key==root->key)
{cout<<"\n found \n";return;}
}
void avl::searchintree(int key)
{
search(root,key);
}
void avl::preorderoftree()
{
preorder(root);
}
int avl::find_min(anode* root)
{
while(root->left!=NULL)
root=root->left;
return root->key;
}
int avl::getbal(anode * root)
{
if(root==NULL)
return 0;
else
return (height(root->left)-height(root->right));
}
void avl::remove(anode * &root,int key)
{
if(root==NULL)
return;
if(root->key>key)
remove(root->left,key);
else if(root->key<key)
remove(root->right,key);
if(root->key==key){
if(root->left!=NULL&&root->right!=NULL)
{
root->key=find_min(root->right);
remove(root->right,root->key);
}
else
{
anode *t=root;
root=(root->left!=NULL)?root->left:root->right;
delete t;
}
}
if(root==NULL) return;
root->height=max(height(root->left),height(root->right));
if (getbal(root) == 2) {
if(getbal(root->left)== -1) rotatewithrightchild(root);
else if(getbal(root->right)==1) doublewithleftchild(root);
}
if (getbal(root)== -2) {
if(getbal(root->right)==-1) rotatewithleftchild(root);
else if(getbal(root->left)== 1) doublewithrightchild(root);
}
}
void avl::removekeyfromtree(int key)
{
remove(root,key);
}
avl::~avl()
{
}
int main()
{
avl a;
a.insertintotree(1);
a.preorderoftree();
a.insertintotree(2);
a.preorderoftree();
a.insertintotree(3);
a.preorderoftree();
a.insertintotree(4);
a.preorderoftree();
a.insertintotree(5);
a.preorderoftree();
a.insertintotree(6);
a.preorderoftree();
a.insertintotree(7);
a.preorderoftree();
a.insertintotree(8);
a.preorderoftree();
a.insertintotree(9);
a.preorderoftree();
a.insertintotree(10);
a.preorderoftree();
a.insertintotree(11);
a.preorderoftree();
a.insertintotree(12);
a.preorderoftree();
a.insertintotree(13);
a.preorderoftree();
a.insertintotree(14);
a.preorderoftree();
a.insertintotree(15);
a.preorderoftree();
printf("\n-------------------------\n");
a.searchintree(1);
printf("\n -------------------------\n");
a.removekeyfromtree(1);
a.removekeyfromtree(10);
a.removekeyfromtree(7);
a.removekeyfromtree(15);
a.removekeyfromtree(5);
a.removekeyfromtree(14);
a.removekeyfromtree(9);
a.removekeyfromtree(11);
a.removekeyfromtree(6);
a.removekeyfromtree(12);
printf("\n");
a.preorderoftree();
}
No comments:
Post a Comment