fork download 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. typedef struct no{
  6.     int pontuacao, id;
  7.     struct no *dir, *esq, *pai;
  8. }No;
  9.  
  10. No *cria_no(int nova_pontuacao, int ID){
  11.     No *novo = malloc(sizeof(No));
  12.     novo->pontuacao = nova_pontuacao;
  13.     novo->dir = novo->esq = NULL;
  14.     novo->id = ID;
  15.     novo->pai = NULL;
  16.     return novo;
  17. }
  18.  
  19. No *insere_no(No *raiz, int nova_pontuacao, int ID){
  20.     No *pai_aux = raiz;
  21.     No *aux = NULL;
  22.     No *nova = cria_no(nova_pontuacao, ID);
  23.     if (raiz == NULL)
  24.         raiz = nova;
  25.     else
  26.     {
  27.         aux = raiz;
  28.         while (aux != NULL)
  29.         {
  30.             pai_aux = aux;
  31.             if (nova_pontuacao < aux->pontuacao)
  32.                 aux = aux->esq;
  33.             else if(nova_pontuacao > aux->pontuacao)
  34.                 aux = aux->dir;
  35.             else if(nova_pontuacao == aux->pontuacao){
  36.                 aux = aux->esq;
  37.                 pai_aux->esq = nova;
  38.                 nova->esq = aux;
  39.                 nova->pai = pai_aux;
  40.                 return raiz;
  41.             }
  42.         }
  43.         nova->pai = pai_aux;
  44.         if (nova_pontuacao < pai_aux->pontuacao)
  45.             pai_aux->esq = nova;
  46.         else if(nova_pontuacao > pai_aux->pontuacao)
  47.             pai_aux->dir = nova;
  48.     }
  49.     return raiz;
  50. }
  51.  
  52. void em_ordem(No *raiz)
  53. {
  54.     if (raiz != NULL)
  55.     {
  56.         em_ordem(raiz->esq);
  57.         printf("%d ", raiz->pontuacao);
  58.         em_ordem(raiz->dir);
  59.     }
  60. }
  61.  
  62. void pre_ordem(No *raiz)
  63. {
  64.     if (raiz != NULL)
  65.     {
  66.         printf("%d ", raiz->pontuacao);
  67.         pre_ordem(raiz->esq);
  68.         pre_ordem(raiz->dir);
  69.     }
  70. }
  71.  
  72. No* sucessor(No *no_remover)
  73. {
  74.  
  75.     // por sucessor
  76.     No *suc = no_remover->dir;
  77.  
  78.     while (suc->esq != NULL)
  79.     {
  80.         suc = suc->esq;
  81.     }
  82.  
  83.     return suc;
  84. }
  85.  
  86. No* antecessor(No *no_remover)
  87. {
  88.  
  89.     // por sucessor
  90.     No *ant = no_remover->esq;
  91.  
  92.     while (ant->dir != NULL)
  93.     {
  94.         ant = ant->dir;
  95.     }
  96.  
  97.     return ant;
  98. }
  99.  
  100. No *remove_noavl(No *raiz, int chave)
  101. {
  102.  
  103.     No *no_remover = raiz;
  104.     No *pai_no_remover = NULL;
  105.     No *copia = NULL;
  106.  
  107.     while (no_remover != NULL && no_remover->pontuacao != chave)
  108.     {
  109.         if (no_remover->pontuacao < chave)
  110.             no_remover = no_remover->dir;
  111.         else
  112.             no_remover = no_remover->esq;
  113.     }
  114.  
  115.     while (no_remover != NULL) // encontrou o valor a ser removido
  116.     {
  117.         if (no_remover->esq == NULL && no_remover->dir == NULL)//eh folha
  118.         {
  119.             if (raiz == no_remover)
  120.             {
  121.                 free(raiz);
  122.                 no_remover = raiz = NULL;
  123.             }
  124.             else
  125.             {
  126.                 if (no_remover->pai->esq != NULL && no_remover->pai->esq->pontuacao == chave)
  127.                     no_remover->pai->esq = NULL;
  128.                 else
  129.                     no_remover->pai->dir = NULL;
  130.  
  131.                 free(no_remover);
  132.                 no_remover = NULL;
  133.             }
  134.         }
  135.         else // tem um filho ou dois filhos
  136.         {
  137.  
  138.             if (no_remover->dir != NULL)
  139.                 copia = sucessor(no_remover);
  140.             else
  141.                 copia = antecessor(no_remover);
  142.  
  143.                 //substitui o valor da ser removido pelo valor
  144.                 //do sucessor ou do antecessor
  145.             no_remover->pontuacao = copia->pontuacao;
  146.             no_remover->id = copia->id;
  147.             //muda o no a ser removido para o sucessor ou antecessor
  148.             no_remover = copia;
  149.             chave = copia->pontuacao;
  150.         }
  151.  
  152.     }
  153.     return raiz;
  154. }
  155.  
  156. No* registrar(No *raiz){
  157.     int pontuacao;
  158.     int id;
  159.     scanf("%d", &id);
  160.     scanf("%d", &pontuacao);
  161.     return insere_no(raiz, pontuacao, id);
  162. }
  163.  
  164. int verifica_existencia(No*raiz, int id, int *pontuacao_velha, int*flag){
  165.     if(raiz != NULL && (*flag) != 1){
  166.         verifica_existencia(raiz->dir, id, pontuacao_velha, flag);
  167.         if(raiz->id == id){
  168.             (*flag) = 1;
  169.             (*pontuacao_velha) = raiz->pontuacao;
  170.         }
  171.         verifica_existencia(raiz->esq, id, pontuacao_velha, flag);
  172.     }
  173. }
  174.  
  175. No* UPDATE(No *raiz){
  176.     int pontuacao_nova, pontuacao_velha, id, flag = 0;
  177.  
  178.     scanf("%d", &id);
  179.     scanf("%d", &pontuacao_nova);
  180.  
  181.     if(raiz != NULL){
  182.         verifica_existencia(raiz, id, &pontuacao_velha, &flag);
  183.  
  184.         if(flag == 1){
  185.             raiz = remove_noavl(raiz, pontuacao_velha);
  186.             raiz = insere_no(raiz, pontuacao_nova, id);
  187.         }
  188.     }
  189.     return raiz;
  190. }
  191.  
  192. int ID_MAX(No *raiz){
  193.     No* aux = raiz;
  194.     while(aux->esq != NULL)
  195.         aux = aux->esq;
  196.     return aux->id;
  197. }
  198.  
  199. void posicao_calc(No *raiz, int id, int *CAT, int *flag){
  200.     if(raiz != NULL && (*flag) != 1){
  201.         posicao_calc(raiz->dir, id, CAT, flag);
  202.         if(raiz->id == id){
  203.             (*flag) = 1;
  204.             (*CAT)++;
  205.         }
  206.         else if((*flag) != 1){
  207.             (*CAT)++;
  208.         }
  209.         posicao_calc(raiz->esq, id, CAT, flag);
  210.     }
  211. }
  212.  
  213. void posicao(No *raiz){
  214.     int id = 0;
  215.     scanf("%d", &id);
  216.  
  217.     if(raiz != NULL){
  218.         int rez_01, rez_02, aux_id, pos;
  219.         rez_01 = rez_02 = aux_id = pos = 0;
  220.  
  221.         aux_id = ID_MAX(raiz);
  222.  
  223.         posicao_calc(raiz, id, &rez_01, &pos);
  224.  
  225.         pos = 0;
  226.  
  227.         posicao_calc(raiz, aux_id, &rez_02, &pos);
  228.  
  229.         if(rez_01>rez_02)
  230.             printf("NOT_FOUND\n");
  231.         else
  232.             printf("%d\n", rez_01);
  233.     }
  234.     else{
  235.         printf("NOT_FOUND\n");
  236.     }
  237.  
  238. }
  239.  
  240. void top(No *raiz){
  241.     if(raiz != NULL){
  242.         No* aux = raiz, *pai_aux = NULL;
  243.         while(aux != NULL){
  244.             pai_aux = aux;
  245.             aux = aux->dir;
  246.         }
  247.         printf("%d\n", pai_aux->id);
  248.     }
  249.     else{
  250.         printf("EMPTY\n");
  251.     }
  252. }
  253.  
  254. void BOTTOM(No *raiz){
  255.     if(raiz != NULL){
  256.         No* aux = raiz, *pai_aux = NULL;
  257.         while(aux != NULL){
  258.             pai_aux = aux;
  259.             aux = aux->esq;
  260.         }
  261.         printf("%d\n", pai_aux->id);
  262.     }
  263.     else{
  264.         printf("EMPTY\n");
  265.     }
  266. }
  267.  
  268. void RANGE_CALC(No *raiz, int pont_min, int pont_max){
  269.     if(raiz != NULL){
  270.         RANGE_CALC(raiz->dir, pont_min, pont_max);
  271.         if(pont_min <= raiz->pontuacao && raiz->pontuacao <= pont_max){
  272.             printf("%d ", raiz->id);
  273.         }
  274.         RANGE_CALC(raiz->esq, pont_min, pont_max);
  275.     }
  276. }
  277.  
  278. void RANGE(No *raiz){
  279.     int min;
  280.     int max;
  281.     min = max = 0;
  282.  
  283.     scanf("%d %d", &min, &max);
  284.     if(raiz != NULL){
  285.         RANGE_CALC(raiz, min, max);
  286.         printf("\n");
  287.     }
  288.     else
  289.         printf("EMPTY\n");
  290. }
  291.  
  292. void COUNT_ABOVE(No *raiz, int ac, int* cont_0x){
  293.     if (raiz != NULL)
  294.     {
  295.         COUNT_ABOVE(raiz->dir, ac, cont_0x);
  296.         if(raiz->pontuacao > ac)
  297.             (*cont_0x)++;
  298.         COUNT_ABOVE(raiz->esq, ac, cont_0x);
  299.     }
  300. }
  301.  
  302. void COUNT_BELOW(No *raiz, int ac, int* cont_0x){
  303.     if (raiz != NULL)
  304.     {
  305.         COUNT_BELOW(raiz->dir, ac, cont_0x);
  306.         if(raiz->pontuacao < ac)
  307.             (*cont_0x)++;
  308.         COUNT_BELOW(raiz->esq, ac, cont_0x);
  309.     }
  310. }
  311.  
  312. int main(){
  313.  
  314. No *ABB = NULL;
  315. int n, cont = 0;
  316. int ac = 0;
  317. int cont_02 = 0;
  318. char rep[20];
  319.  
  320. scanf("%d", &n);
  321.  
  322. while(cont < n){
  323.     strcpy(rep," ");
  324.     fflush(stdin);
  325.     scanf("%s", &rep);
  326.  
  327.     if(strcmp(rep, "REGISTER") == 0)
  328.         ABB = registrar(ABB); 
  329.     else if(strcmp(rep, "UPDATE") == 0)
  330.         ABB = UPDATE(ABB);    
  331.     else if(strcmp(rep, "POSITION") == 0)
  332.         posicao(ABB);
  333.     else if(strcmp(rep, "RANGE") == 0)
  334.         RANGE(ABB);
  335.     else if(strcmp(rep, "TOP") == 0)
  336.         top(ABB);
  337.     else if(strcmp(rep, "BOTTOM") == 0)
  338.         BOTTOM(ABB);
  339.     else if(strcmp(rep, "COUNT_ABOVE") == 0){
  340.         ac = cont_02 = 0;
  341.         scanf("%d", &ac);
  342.         COUNT_ABOVE(ABB, ac, &cont_02);
  343.         printf("%d\n", cont_02);
  344.     }
  345.     else if(strcmp(rep, "COUNT_BELOW") == 0){
  346.         ac = cont_02 = 0;
  347.         scanf("%d", &ac);
  348.         COUNT_BELOW(ABB, ac, &cont_02);
  349.         printf("%d\n", cont_02);
  350.     }
  351.     cont++;
  352. }
  353.  
  354. return 0;}
Success #stdin #stdout 0s 5288KB
comments (?)
stdin 
18
TOP
BOTTOM
RANGE 1000 2000
COUNT_ABOVE 1500
COUNT_BELOW 1500
POSITION 999
REGISTER 301 1750
REGISTER 302 1250
REGISTER 303 2250
REGISTER 304 1750
TOP
BOTTOM
RANGE 1700 1800
COUNT_ABOVE 1750
COUNT_BELOW 1750
POSITION 301
UPDATE 302 2750
TOP
stdout 
EMPTY
EMPTY
EMPTY
0
0
NOT_FOUND
303
302
301 304 
1
1
2
302
https://ideone.com/dNLcoV
language:
C (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!