Advertisement
Eternoseeker

AVL tree DSA

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