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