[text] insert2

Viewer

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. struct node{
  5.         int data;
  6.         node *L, *R;
  7. };
  8.  
  9. class AVL{
  10. public:
  11.         node *root;
  12.  
  13.         AVL(){
  14.                 root=NULL;
  15.         }
  16.         int height(node *temp);
  17.         int max(int a, int b);
  18. //      int balancefactor(node *n);
  19.         node *LL(node *);
  20.         node *RR(node *);
  21.         node *LR(node *);
  22.         node *RL(node *);
  23.         node *getroot(){
  24.                 return this->root;
  25.         }
  26.         node *insert(node *temp,int key){
  27. //              node *temp=root;
  28.                 node *nn=new node;
  29.                 nn->data=key;
  30.                 nn->L=NULL;
  31.                 nn->R=NULL;
  32.                 if(temp==NULL){
  33.                         temp=new node;
  34.                         temp->data=key;
  35.                         temp->L=temp->R=NULL;
  36.                 }
  37.                 else{
  38.                         if(key<temp->data){
  39.                                 temp->L=insert(temp->L,key);
  40.                                 if((height(temp->L))-height(temp->R)==2){
  41.                                         if(key<temp->L->data)
  42.                                                 temp=LL(temp);
  43.                                         else
  44.                                                 temp=LR(temp);
  45.                                 }
  46.                         }
  47.                         else{
  48.                                 temp->R=insert(temp->R,key);
  49.                                 if((height(temp->L))-height(temp->R)==-2){
  50.                                         if(key<temp->L->data)
  51.                                                 temp=RR(temp);
  52.                                         else
  53.                                                 temp=RL(temp);
  54.                                 }
  55.                         }
  56.                 }
  57.                 return temp;
  58.         }
  59.     void inorder(node *t){
  60.             if(t!=NULL){
  61.              inorder(t->L);
  62.              cout<<t->data<<" ";
  63.              inorder(t->R);
  64.             }
  65.  
  66.         }
  67. };
  68.  
  69. int AVL::max(int a, int b){
  70.         return (a > b)?a:b;
  71. }
  72.  
  73. int AVL:: height(node *temp){
  74.         if(temp == NULL){
  75.                 return -1;
  76.         }
  77.         if(temp -> L == NULL && temp -> R == NULL){
  78.                 return 0;
  79.         }
  80.         return(1 + max(height(temp -> L), height(temp -> R)));
  81. }
  82.  
  83. /*
  84. int AVL::balancefactor(node *n){
  85.         if (n == NULL){
  86.                 return 0;
  87.         }
  88.         return height(n -> L) - height( n-> R);
  89. }
  90. */
  91.  
  92. node * AVL:: LL(node *parent){
  93.         node *temp = parent -> L;
  94.         parent -> L = temp -> R;
  95.         temp -> R = parent;
  96.         return temp;
  97. }
  98.  
  99. node * AVL:: RR(node *parent){
  100.         node *temp = parent -> R;
  101.         parent -> R = temp -> L;
  102.         temp -> L = parent;
  103.         return temp;
  104. }
  105.  
  106. node * AVL:: LR(node *parent){
  107.         parent -> R = RR(parent -> L);
  108.         parent = LL(parent);
  109.         return parent;
  110. }
  111.  
  112. node * AVL:: RL(node *parent){
  113.         parent -> R = RR(parent -> R);
  114.         parent = LL(parent);
  115.         return parent;
  116. }
  117.  
  118. int main(){
  119.         AVL a;
  120.         a.insert(a.root, 10);
  121.         a.inorder(a.root);
  122. }
  123.  

Editor

You can edit this paste and save as new:


File Description
  • insert2
  • Paste Code
  • 07 Dec-2022
  • 2.05 Kb
You can Share it: