C++ program to find an element into AVL tree














































C++ program to find an element into AVL tree



//Enter Your Code Here...#include <iostream>
using namespace std;
struct node
{
int value;
struct node *right;
struct node *left;
int height;
};
class avl
{
public:int height(struct node *y)
{
if(y==NULL)
{
return 0;
}else
{
return y->height;
}
}
int max(int a,int b)
{
if(a>b)
{
return a;
}
return b;
}
struct node *newnode(int data)
{
node *temp=new node();
temp->value=data;
temp->left=temp->right=NULL;
temp->height=1;
return temp;
}
struct node *leftrotate(struct node *y)
{
struct node *x=y->right;
struct node *t2=x->left;
x->left=y;
y->right=t2;
y->height=max(height(y->right),height(y->left))+1;
    x->height=max(height(x->right),height(x->left))+1;
return x;
}
struct node *rightrotate(struct node *x)
{
struct node *y=x->left;
struct node *t2=y->right;
y->right=x;
x->left=t2;
x->height=max(height(x->right),height(x->left))+1;
y->height=max(height(y->right),height(y->left))+1;
return y;
}
int balancefactor(struct node *root)
  {
   if(root==NULL)
  {
   return 0;
  }
   else
   {
    return (height(root->left)-height(root->right));
   }
  }
    struct node* insert(struct node *root,int value)
  {
    if(root==NULL)
    {
     return (newnode(value));
    }
    if(value<root->value)
    {
      root->left=insert(root->left,value);
    }
    else if(value>root->value)
    {
    root->right=insert(root->right,value);
    }
    else
    {
    return root;
    }
  root->height=1+max(height(root->left),height(root->right));
    int balance=balancefactor(root);
    if(balance>1 && value<root->left->value)
    {
     return rightrotate(root);
    }
    if(balance>1 && value>root->left->value)
    {
    root->left=leftrotate(root->left);
     return rightrotate(root);
    }
    if(balance<-1 && value>root->right->value)
    {
     return leftrotate(root);
    }
    if(balance<-1 && value<root->right->value)
    {
    root->right=rightrotate(root->right);
     return leftrotate(root);
    }
    return root;
  }
    void preorder(struct node *root)
  {
   if(root!=NULL)
   {
   cout<<root->value<<" ";
   preorder(root->left);
   preorder(root->right);
   }
  }
  void inorder(struct node *root) 
{ if (root!=NULL) 
{
    inorder(root->left); 
    cout << root->value<< " "; 
    inorder(root->right); 
}
}
void postorder(struct node *root) 
    if (root!=NULL) 
   { postorder(root->left); 
    postorder(root->right); 
    cout <<root->value<< " "; 
  } 
}
bool b=false;
bool search(struct node* root, int key) 
     {
         if(root!=NULL)
  {  if (root->value == key) 
       {
           b=true;
       }
    else if (root->value< key) 
       { 
           search(root->right, key); 
       }else 
         {
             search(root->left, key); 
         }
  }
  return b;
       } 
};
int main()
{
   struct node *root=NULL;
     avl T;
    root=T.insert(root,100);
    root=T.insert(root,250);
root=T.insert(root,370);
root=T.insert(root,400);
root=T.insert(root,520);
root=T.insert(root,260);
if(T.search(root,310))
{
    cout<<"Element find"<<endl;
}else
{
    cout<<"Element not present in tree"<<endl;
}
if(T.search(root,370))
{
    cout<<"Element find"<<endl;
}else
{
    cout<<"Element not present in tree"<<endl;
}
return 0;
} /* The constructed AVL Tree would be
            370
           /  \
         250   400
        /  \     \
       100  260    520
  */

output:
Element not present in tree
Element find

Comments