lib/Documentation/docs-sonyckson/AVL2.cpp

   1 #include <cstdio>
   2 #include <iostream>
   3 #include <cstdlib>
   4 using namespace std;
   5 struct node{
   6         int val;
   7         int h;
   8         int contador;
   9         struct node *l, *r, *p;
  10 };
  11 struct node *root;
  12 int BI(struct node* r ){        /// INDICE DE BALANCEO
  13         if( r == NULL ) return 0;
  14         if( r->l && r->r ){
  15                 return r->r->h - r->l->h;
  16         }else if( r->l ){
  17                 return -r->l->h-1;
  18         }else if( r->r ) return r->r->h+1;
  19         else return 0;
  20 }
  21 void suplantar(struct node* p, struct node* h, struct node* n){
  22         if( p == NULL )root = n;
  23         else if( p->l == h )p->l = n;
  24         else p->r = n;
  25 }
  26 int maxAltura(struct node* r){
  27         r->h = 0;
  28         if( r->l && r->h < r->l->h + 1 ) r->h = r->l->h + 1;
  29         if( r->r && r->h < r->r->h + 1 ) r->h = r->r->h + 1;
  30 }
  31 void RIGHT(struct node* r){
  32         struct node* aux = r->l;
  33         r->l = aux->r;
  34         if( r->l ){
  35                 r->l->p = r;
  36         }
  37         suplantar(r->p, r, aux);
  38         aux->p = r->p;
  39         r->p = aux;
  40         aux->r = r;
  41         maxAltura(r);
  42         maxAltura(aux);
  43 }
  44 void LEFT(struct node* r){
  45         struct node* aux = r->r;
  46         r->r = aux->l;
  47         if( r->r ){
  48                 r->r->p = r;
  49         }
  50         suplantar(r->p, r, aux);
  51         aux->p = r->p;
  52         r->p = aux;
  53         aux->l = r;
  54         maxAltura(r);
  55         maxAltura(aux);
  56 }
  57 void balanceo(struct node* r ){
  58         if( !r ) return;
  59         maxAltura(r);
  60         int balanceIndex = BI(r);
  61         if( abs(balanceIndex) < 2 ) return;
  62         if( balanceIndex == 2 ){
  63                 int bis = BI(r->r);
  64                 if( bis == -1 ){
  65                         RIGHT(r->r);
  66                 }
  67                 LEFT(r);
  68         }else{
  69                 int bis = BI(r->l);
  70                 if( bis == 1 ){
  71                         LEFT(r->l);
  72                 }RIGHT(r);
  73         }
  74 }
  75 struct node *nuevo(int val, struct node* r ){
  76         struct node *a = new node;
  77         a->val = val, a->l = a->r = NULL;
  78         a->p = r, a->contador = 1;
  79         a->h = 0;
  80         return a;
  81 }
  82 void insertr(int val, struct node *r){
  83         if( r->val == val ){
  84                 r->contador++;return;
  85         }if( r->val > val ){
  86                 if( r->l == NULL ){
  87                         struct node *a = nuevo(val,r);
  88                         r->l = a;
  89                         r->h = 1;
  90                         return;
  91                 }else{
  92                         insertr(val,r->l);
  93                 }
  94         }else{
  95                 if( r->r == NULL ){
  96                         struct node *a = nuevo(val,r);
  97                         r->r = a;
  98                         r->h = 1;
  99                         return;
 100                 }else{
 101                         insertr(val, r->r);
 102                 }
 103         }
 104         balanceo(r);
 105 }
 106 void insert(int val){
 107         if( root == NULL ){
 108                 root = new node;
 109                 root->l = root->r = root->p = NULL;
 110                 root->val = val, root->contador = 1, root->h = 0;
 111                 return;
 112         }
 113         struct node * aux = root;
 114         insertr(val,root);
 115 }
 116 int borrarMax(struct node* r){
 117         int res;
 118         struct node* a = r;
 119         if( r->r ) res = borrarMax(r->r);
 120         else{
 121                 a = r->p;
 122                 suplantar(r->p, r, r->l);
 123                 if( r->l ) r->l->p = r->p;
 124                 res = r->val;
 125                 delete r;
 126         }
 127         r = a;
 128         balanceo(r);
 129         return res;
 130 }
 131 void deleteval(int val, struct node* r){
 132         if( !r ) return;
 133         struct node *a = r;
 134         if(r->val == val ){
 135                 if( !r->l ){
 136                         suplantar(r->p, r, r->r);
 137                         a = r->p;
 138                         if( r->r )r->r->p = r->p;
 139                         delete r;
 140                 }else if( !r->r ){
 141                         suplantar(r->p, r, r->l);
 142                         a = r->p;
 143                         if( r->l )r->l->p = r->p;
 144                         delete r;
 145                 }else{
 146                         int v = borrarMax(r->l);
 147                         r->val = v;
 148                 }
 149         }else if( r->val > val ){
 150                 deleteval(val, r->l);
 151         }else deleteval(val, r->r);
 152         r = a;
 153         if( !r ) return;
 154         balanceo(r);
 155 }
 156 int search(int val, struct node* r){
 157         if( !r ) return 0; if( r->val == val ) return 1;
 158         if( r->val > val ) return search(val, r->l);else return search(val, r->r);
 159 }
 160 void dfs(struct node * r ){
 161         if( r == NULL ) return;
 162         printf(" %i ", r->val);
 163         printf("(");
 164         dfs(r->l);
 165         printf(")");
 166         printf("(");
 167         dfs(r->r);
 168         printf(")");
 169 }
 170 int main(){
 171         int i,j ,k;
 172         root = NULL;
 173         // testeo...
 174         printf("Introduzca números para el árbol:\n");
 175         while(1){
 176                 scanf("%i", &i);
 177                 scanf("%i", &k);
 178                 if( i == 1 )
 179                 insert(k);
 180                 else if( i == 2 ){
 181                         if( search(k, root) ) printf("Si esta!!!\n");
 182                         else printf("No esta!!!\n");
 183                 }else deleteval(k,root);
 184                 dfs(root);
 185                 printf("\n");
 186         }
 187         return 0;
 188 }