Documentation/docs-sonyckson/TREAPS.cpp

   1 #include <cstdio>
   2 #include <set>
   3 #include <cassert>
   4 #include <iostream>
   5 #include <cstdlib>
   6 using namespace std;
   7 struct node{
   8         int val;
   9         int p;
  10         struct node * l,* r;
  11         int hijos;
  12 };
  13 struct node* root;
  14 struct node* RIGHT(struct node * n){
  15         struct node* aux = n->l;
  16         n->hijos -= ( aux->hijos + 1 );
  17         aux->hijos += n->hijos+1;
  18         if( aux->r ) n->hijos += aux->r->hijos + 1; //, aux->hijos -= aux->r->hijos;
  19         n->l = aux->r;
  20         aux->r = n;
  21         return aux;
  22 }
  23 struct node* LEFT(struct node * n){
  24         struct node* aux = n->r;
  25         n->hijos -= (aux->hijos + 1 );
  26         aux->hijos += n->hijos + 1;
  27         if( aux->l ) n->hijos += aux->l->hijos + 1; //, aux->hijos -= aux->l->hijos;
  28         n->r = aux->l;
  29         aux->l = n;
  30         return aux;
  31 }
  32 struct node * insert(int val, struct node * r){
  33         if( r == NULL ){
  34                 struct node * a = new node;
  35                 a->p = rand(), a->val = val, a->l = a->r = NULL, a->hijos = 0;
  36                 return a;
  37         }
  38         r->hijos++;
  39         if( val < r->val ){
  40                 r->l = insert(val, r->l);
  41                 if( r->l->p > r->p ){
  42                         return RIGHT(r);
  43                 }
  44         }else if( val > r->val ){
  45                 r->r = insert(val, r->r);
  46                 if( r->r->p > r->p ){
  47                         return LEFT(r);
  48                 }
  49         }
  50         return r;
  51 }
  52 struct node* bubbleDown(struct node* n){
  53         struct node* aux = n;
  54         if( n->l == n->r ){
  55                 delete n;
  56                 return NULL;
  57         }else if( n->l && n->r ){
  58                 if( n->l->p > n->r->p ){
  59                         aux = RIGHT(n);
  60                         aux->r = bubbleDown(aux->r);
  61                 }else{
  62                         aux = LEFT(n);
  63                         aux->l = bubbleDown(aux->l);
  64                 }
  65         }else if( n->l ){
  66                 aux = RIGHT(n);
  67                 aux->r = bubbleDown(aux->r);
  68         }else{
  69                 aux = LEFT(n);
  70                 aux->l = bubbleDown(aux->l);
  71         }
  72         aux->hijos--;
  73         return aux;
  74 }
  75 // PRECONDICIÖN: val esta en el árbol
  76 struct node* deleteval(int val, struct node* n){
  77         if( !n ) return NULL;
  78         if( n->val != val ) n->hijos--;
  79         if( n->val > val ) n->l = deleteval(val, n->l);
  80         else if( n->val < val ) n->r = deleteval(val,n->r);
  81         else n = bubbleDown(n);
  82         return n;
  83 }
  84 bool search(int val, struct node* n ){
  85         if( !n ) return false;
  86         if( n->val == val ) return true;
  87         if( n->val > val ) return search(val, n->l);
  88         if( n->val < val ) return search(val, n->r);
  89 }
  90 void dfs(struct node * r ){
  91         if( r == NULL ) return;
  92         printf(" %i p%i h%i ", r->val, r->p, r->hijos);
  93         printf("(");
  94         dfs(r->l);
  95         printf(")");
  96         printf("(");
  97         dfs(r->r);
  98         printf(")");
  99 }
 100 int main(){
 101         int i,j ,k;
 102         root = NULL;
 103         // testeo...
 104         srand(-1);
 105         printf("Introduzca números para el árbol ( 1 x insertar... 2 x buscar, 0 x borrar:\n");
 106         while(1){
 107                 scanf("%i", &i);
 108                 scanf("%i", &k);
 109                 if( i == 1 )
 110                         root = insert(k, root);
 111                 else if( i == 2 ){
 112                         if( search(k, root) ) printf("Si esta!!!\n");
 113                         else printf("No esta!!!\n");
 114                 }
 115                 else if( search(k, root) ) root = deleteval(k,root);
 116                 dfs(root);
 117                 printf("\n");
 118         }
 119         return 0;
 120 }