[text] vt

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.         node *root;
  11.         public:
  12.         AVL(){
  13.                 root=NULL;
  14.         }
  15.         int height(node *temp);
  16.         int max(int a, int b);
  17.  
  18.         node* LL(node *);
  19.         node* RR(node *);
  20.         node* LR(node *);
  21.         node* RL(node *);
  22.         node* insert(node* temp,int key);
  23. };
  24.  
  25. int AVL::max(int a, int b){
  26.         return (a > b)?a:b;
  27. }
  28.  
  29. int AVL:: height(node *temp){
  30.         if(temp == NULL){
  31.                 return -1;
  32.         }
  33.         if(temp -> L == NULL && temp -> R == NULL){
  34.                 return 0;
  35.         }
  36.         return(1 + max(height(temp -> L), height(temp -> R)));
  37. }
  38.  
  39.  
  40.  
  41. node * AVL:: LL(node *parent){
  42.         node *temp = parent -> L;
  43.         parent -> L = temp -> R;
  44.         temp -> R = parent;
  45.         return temp;
  46. }
  47.  
  48. node * AVL:: RR(node *parent){
  49.         node *temp = parent -> R;
  50.         parent -> R = temp -> L;
  51.         temp -> L = parent;
  52.         return temp;
  53. }
  54.  
  55. node * AVL:: LR(node *parent){
  56.         parent -> R = RR(parent -> L);
  57.         parent = LL(parent);
  58.         return parent;
  59. }
  60.  
  61. node * AVL:: RL(node *parent){
  62.         parent -> R = RR(parent -> R);
  63.         parent = LL(parent);
  64.         return parent;
  65. }
  66.  
  67. node* AVL::insert(node* temp,int key){
  68.                         node *nn=new node;
  69.                         nn->data=key;
  70.                         nn->L=NULL;
  71.                         nn->R=NULL;
  72.                         if(temp==NULL){
  73.                                 temp=new node;
  74.                                 temp->data=key;
  75.                                 temp->L=temp->R=NULL;
  76.                         }
  77.                         else{
  78.                                 if(key<temp->data){
  79.                                         temp->L=insert(temp->L,key);
  80.                                         if((height(temp->L))-height(temp->R)==2){
  81.                                                 if(key<temp->L->data)
  82.                                                         temp=LL(temp);
  83.                                                 else
  84.                                                         temp=LR(temp);
  85.                                         }
  86.                                 }
  87.                                 else{
  88.                                         temp->R=insert(temp->R,key);
  89.                                         if((height(temp->L))-height(temp->R)==-2){
  90.                                                 if(key<temp->L->data)
  91.                                                         temp=RR(temp);
  92.                                                 else
  93.                                                         temp=RL(temp);
  94.                                         }
  95.                                 }
  96.                         }
  97.                         return temp;
  98.                 }
  99.  
  100. int main(){
  101.         AVL b;
  102.         b.insert(b.root,5);
  103.         return 0;
  104. }
  105.  
  106.  
  107.  

Editor

You can edit this paste and save as new:


File Description
  • vt
  • Paste Code
  • 07 Dec-2022
  • 1.74 Kb
You can Share it: