Advertisement
hadiuzzaman65

insert element in bst

Apr 27th, 2019
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. typedef struct mylist
  5. {
  6.     int data;
  7.     mylist *left;
  8.     mylist *right;
  9.     int height;
  10. } node;
  11. int max(int a,int b)
  12. {
  13.     return (a>b)? a:b;
  14. }
  15. int height(node *temp)
  16. {
  17.     if(temp==NULL)
  18.         return 0;
  19.     return temp->height;
  20. }
  21. node *newnode(int item)
  22. {
  23.     node *temp;
  24.     temp=new node;
  25.  
  26.     temp->data=item;
  27.     temp->left=NULL;
  28.     temp->right=NULL;
  29.     temp->height=1;
  30.     return temp;
  31. }
  32. node *rightrotate(node *temp)
  33. {
  34.     node *x=temp->left;
  35.     node *m=x->right;
  36.     x->right=temp;
  37.     temp->left=m;
  38.     temp->height=max(height(temp->left),height(temp->right))+1;
  39.     x->height=max(height(temp->left),height(temp->right))+1;
  40.     return x;
  41. }
  42. node *leftrotate(node *temp)
  43. {
  44.     node *x=temp->right;
  45.     node *m=x->left;
  46.     x->left=temp;
  47.     temp->right=m;
  48.     temp->height=max(height(temp->left),height(temp->right))+1;
  49.     x->height=max(height(temp->left),height(temp->right))+1;
  50.     return x;
  51. }
  52. int isbalance(node *temp)
  53. {
  54.     if(temp==NULL)
  55.         return 0;
  56.     return height(temp->left)-height(temp->right);
  57. }
  58. node *insert(node *root,int key)
  59. {
  60.     if(root==NULL)
  61.         return (newnode(key));
  62.     if(key<root->data)
  63.     {
  64.         root->left=insert(root->left,key);
  65.     }
  66.     else if(key>root->data)
  67.     {
  68.         root->right=insert(root->right,key);
  69.     }
  70.     else
  71.         return root;
  72.     root->height=max(height(root->left),height(root->right))+1;
  73.     int balance=isbalance(root);
  74.     if(balance>1&&key<root->left->data)
  75.     {
  76.         return rightrotate(root);
  77.     }
  78.     if(balance<-1&&key>root->right->data)
  79.     {
  80.         return leftrotate(root);
  81.     }
  82.     if(balance>1&&key>root->left->data)
  83.     {
  84.         root->left=leftrotate(root->left);
  85.         return rightrotate(root);
  86.     }
  87.     if(balance<-1&&key<root->right->data)
  88.     {
  89.         root->right=rightrotate(root->right);
  90.         return leftrotate(root);
  91.     }
  92.     return root;
  93.  
  94. }
  95. int main()
  96. {
  97.     node *root=NULL;
  98.     root=insert(root,8);
  99.     root= insert(root,9);
  100.     root=insert(root,2);
  101.     root= insert(root,13);
  102.     root= insert(root,4);
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement