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