lib/Documentation/docs-sonyckson/SPLAY.cpp

   1 #include <cstdio>
   2 #include <cstdlib>
   3 #include <iostream>
   4 using namespace std;
   5 struct node{
   6         struct node *l, *r;
   7         int val;
   8 };
   9 struct node *root;
  10 struct node *aux1, *aux2;
  11 struct node *splay(struct node *n, int val){
  12         struct node N, *l, *r;
  13         l = r = &N;
  14         N.l = N.r = NULL;
  15         struct node *y;
  16         while(1){
  17                 if( n->val > val ){
  18                         if( !n->l ) break;
  19                         if( n->l->val > val ){
  20                                 y = n->l;
  21                                 n->l = y->r;
  22                                 y->r = n;
  23                                 n = y;
  24                                 if( !n->l ) break;
  25                         }
  26                         r->l = n;
  27                         r = n;
  28                         n = n->l;
  29                 }else if( n->val < val ){
  30                         if( !n->r ) break;
  31                         if( n->r->val < val ){
  32                                 y = n->r;
  33                                 n->r = y->l;
  34                                 y->l = n;
  35                                 n = y;
  36                                 if( !n->r ) break;
  37                         }
  38                         l->r = n;
  39                         l = n;
  40                         n = n->r;
  41                 }else break;
  42         }
  43         r->l = n->r;
  44         l->r = n->l;
  45         n->r = N.l;
  46         n->l = N.r;
  47         return n;
  48 }
  49 struct node *S1, *S2;
  50 void split(struct node *T, int k ){
  51         if( !T ) { S1 = S2 = NULL ; return ; }
  52         struct node *aux = splay(T,k);
  53         if( aux->val <= k ){
  54                 S2 = aux->r;
  55                 aux->r = NULL;
  56                 S1 = aux;
  57         }else{
  58                 S1 = aux->l;
  59                 aux->l = NULL;
  60                 S2 = aux;
  61         }
  62 }
  63 struct node *join(struct node *T1, struct node *T2){
  64         if( T1 == NULL ) return T2;
  65         if( T2 == NULL ) return T1;
  66         T1 = splay(T1, INT_MAX);
  67         T1->r = T2;
  68         return T1;
  69 }
  70 struct node *insert(struct node *T, int k){
  71         struct node *aux = new node;
  72         aux->val = k;
  73         split(T, k);
  74         aux->l = S1;
  75         aux->r = S2;
  76         return aux;
  77 }
  78 struct node *deleteval(struct node *T, int k){
  79         if( T == NULL ) return T;
  80         T = splay(T, k);
  81         if( T->val == k ){
  82                 S1 = T->l;
  83                 S2 = T->r;
  84                 delete T;
  85                 T = join(S1, S2);
  86         }
  87         return T;
  88 }
  89
  90 void dfs(struct node * r ){
  91         if( r == NULL ) return;
  92         printf(" %i ", r->val);
  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         printf("Introduzca números para el árbol ( 1 x insertar... 2 x buscar, 0 x borrar:\n");
 105         while(1){
 106                 scanf("%i", &i);
 107                 scanf("%i", &k);
 108                 if( i == 1 )root = insert(root, k);
 109                 else if( i == 2 ){
 110                         root = splay( root, k );
 111                         if( root &&  root->val == k  ) printf("Si esta!!!\n");
 112                         else printf("No esta!!!\n");
 113                 }
 114                 else root = deleteval(root, k);
 115                 dfs(root);
 116                 printf("\n");
 117         }
 118         return 0;
 119 }