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
  40.             pai_aux->dir = 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("EMPTY\n");
  224.         else
  225.             printf("%d\n", rez_01);
  226.     }
  227.  
  228. }
  229.  
  230. void top(No *raiz){
  231.     if(raiz != NULL){
  232.         No* aux = raiz;
  233.         while(aux->dir != NULL)
  234.             aux = aux->dir;
  235.         printf("%d\n", aux->id);
  236.     }
  237.     else{
  238.         printf("EMPTY\n");
  239.     }
  240. }
  241.  
  242. void BOTTOM(No *raiz){
  243.     if(raiz != NULL){
  244.         No* aux = raiz;
  245.         while(aux->esq != NULL)
  246.             aux = aux->esq;
  247.         printf("%d\n", aux->id);
  248.     }
  249.     else{
  250.         printf("EMPTY\n");
  251.     }
  252.  
  253. }
  254.  
  255. void RANGE_CALC(No *raiz, int pont_min, int pont_max){
  256.     if(raiz != NULL){
  257.         RANGE_CALC(raiz->dir, pont_min, pont_max);
  258.         if(pont_min <= raiz->pontuacao && raiz->pontuacao <= pont_max){
  259.             printf("%d ", raiz->id);
  260.         }
  261.         RANGE_CALC(raiz->esq, pont_min, pont_max);
  262.     }
  263. }
  264.  
  265. void RANGE(No *raiz){
  266.     int min;
  267.     int max;
  268.     min = max = 0;
  269.  
  270.     scanf("%d %d", &min, &max);
  271.     if(raiz != NULL){
  272.         RANGE_CALC(raiz, min, max);
  273.         printf("\n");
  274.     }
  275.     else
  276.         printf("EMPTY\n");
  277. }
  278.  
  279. void COUNT_ABOVE(No *raiz, int ac, int* cont_0x){
  280.     if (raiz != NULL)
  281.     {
  282.         COUNT_ABOVE(raiz->dir, ac, cont_0x);
  283.         if(raiz->pontuacao > ac)
  284.             (*cont_0x)++;
  285.         COUNT_ABOVE(raiz->esq, ac, cont_0x);
  286.     }
  287. }
  288.  
  289. void COUNT_BELOW(No *raiz, int ac, int* cont_0x){
  290.     if (raiz != NULL)
  291.     {
  292.         COUNT_BELOW(raiz->dir, ac, cont_0x);
  293.         if(raiz->pontuacao < ac)
  294.             (*cont_0x)++;
  295.         COUNT_BELOW(raiz->esq, ac, cont_0x);
  296.     }
  297. }
  298.  
  299. int main(){
  300.  
  301. No *ABB = NULL;
  302. int n, cont = 0;
  303. int ac = 0;
  304. int cont_02 = 0;
  305. char rep[20];
  306.  
  307. scanf("%d", &n);
  308.  
  309. while(cont < n){
  310.     strcpy(rep," ");
  311.     fflush(stdin);
  312.     scanf("%s", &rep);
  313.  
  314.     if(strcmp(rep, "REGISTER") == 0)
  315.         ABB = registrar(ABB); 
  316.     else if(strcmp(rep, "UPDATE") == 0)
  317.         ABB = UPDATE(ABB);    
  318.     else if(strcmp(rep, "POSITION") == 0)
  319.         posicao(ABB);
  320.     else if(strcmp(rep, "RANGE") == 0)
  321.         RANGE(ABB);
  322.     else if(strcmp(rep, "TOP") == 0)
  323.         top(ABB);
  324.     else if(strcmp(rep, "BOTTOM") == 0)
  325.         BOTTOM(ABB);
  326.     else if(strcmp(rep, "COUNT_ABOVE") == 0){
  327.         ac = cont_02 = 0;
  328.         scanf("%d", &ac);
  329.         COUNT_ABOVE(ABB, ac, &cont_02);
  330.         printf("%d\n", cont_02);
  331.     }
  332.     else if(strcmp(rep, "COUNT_BELOW") == 0){
  333.         ac = cont_02 = 0;
  334.         scanf("%d", &ac);
  335.         COUNT_BELOW(ABB, ac, &cont_02);
  336.         printf("%d\n", cont_02);
  337.     }
  338.     cont++;
  339. }
  340.  
  341. return 0;}
Success #stdin #stdout 0s 5320KB
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/eqSUuP
language:
C (gcc 8.3)
created:
15 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!