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 = 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("NOT_FOUND\n");
  236.         else
  237.             printf("%d\n", rez_01);
  238.     }
  239.     else{
  240.         printf("NOT_FOUND\n");
  241.     }
  242.  
  243. }
  244.  
  245. void top(No *raiz){
  246.     if(raiz != NULL){
  247.         No* aux = raiz;
  248.         while(aux->dir != NULL)
  249.             aux = aux->dir;
  250.         printf("%d\n", aux->id);
  251.     }
  252.     else{
  253.         printf("EMPTY\n");
  254.     }
  255. }
  256.  
  257. void BOTTOM(No *raiz){
  258.     if(raiz != NULL){
  259.         No* aux = raiz;
  260.         while(aux->esq != NULL)
  261.             aux = aux->esq;
  262.         printf("%d\n", aux->id);
  263.     }
  264.     else{
  265.         printf("EMPTY\n");
  266.     }
  267.  
  268. }
  269.  
  270. void RANGE_CALC(No *raiz, int pont_min, int pont_max){
  271.     if(raiz != NULL){
  272.         RANGE_CALC(raiz->dir, pont_min, pont_max);
  273.         if(pont_min <= raiz->pontuacao && raiz->pontuacao <= pont_max){
  274.             printf("%d ", raiz->id);
  275.         }
  276.         RANGE_CALC(raiz->esq, pont_min, pont_max);
  277.     }
  278. }
  279.  
  280. void RANGE(No *raiz){
  281.     int min;
  282.     int max;
  283.     min = max = 0;
  284.  
  285.     scanf("%d %d", &min, &max);
  286.     if(raiz != NULL){
  287.         RANGE_CALC(raiz, min, max);
  288.         printf("\n");
  289.     }
  290.     else
  291.         printf("EMPTY\n");
  292. }
  293.  
  294. void COUNT_ABOVE(No *raiz, int ac, int* cont_0x){
  295.     if (raiz != NULL)
  296.     {
  297.         COUNT_ABOVE(raiz->dir, ac, cont_0x);
  298.         if(raiz->pontuacao > ac)
  299.             (*cont_0x)++;
  300.         COUNT_ABOVE(raiz->esq, ac, cont_0x);
  301.     }
  302. }
  303.  
  304. void COUNT_BELOW(No *raiz, int ac, int* cont_0x){
  305.     if (raiz != NULL)
  306.     {
  307.         COUNT_BELOW(raiz->dir, ac, cont_0x);
  308.         if(raiz->pontuacao < ac)
  309.             (*cont_0x)++;
  310.         COUNT_BELOW(raiz->esq, ac, cont_0x);
  311.     }
  312. }
  313.  
  314. int main(){
  315.  
  316. No *ABB = NULL;
  317. int n, cont = 0;
  318. int ac = 0;
  319. int cont_02 = 0;
  320. char rep[20];
  321.  
  322. scanf("%d", &n);
  323.  
  324. while(cont < n){
  325.     strcpy(rep," ");
  326.     fflush(stdin);
  327.     scanf("%s", &rep);
  328.  
  329.     if(strcmp(rep, "REGISTER") == 0)
  330.         ABB = registrar(ABB); 
  331.     else if(strcmp(rep, "UPDATE") == 0)
  332.         ABB = UPDATE(ABB);    
  333.     else if(strcmp(rep, "POSITION") == 0)
  334.         posicao(ABB);
  335.     else if(strcmp(rep, "RANGE") == 0)
  336.         RANGE(ABB);
  337.     else if(strcmp(rep, "TOP") == 0)
  338.         top(ABB);
  339.     else if(strcmp(rep, "BOTTOM") == 0)
  340.         BOTTOM(ABB);
  341.     else if(strcmp(rep, "COUNT_ABOVE") == 0){
  342.         ac = cont_02 = 0;
  343.         scanf("%d", &ac);
  344.         COUNT_ABOVE(ABB, ac, &cont_02);
  345.         printf("%d\n", cont_02);
  346.     }
  347.     else if(strcmp(rep, "COUNT_BELOW") == 0){
  348.         ac = cont_02 = 0;
  349.         scanf("%d", &ac);
  350.         COUNT_BELOW(ABB, ac, &cont_02);
  351.         printf("%d\n", cont_02);
  352.     }
  353.     cont++;
  354. }
  355.  
  356. return 0;}
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
15
REGISTER 201 2000
REGISTER 202 2000
REGISTER 203 1500
REGISTER 204 2500
REGISTER 205 1500
TOP
BOTTOM
RANGE 2000 2000
RANGE 1500 1500
COUNT_ABOVE 1999
COUNT_BELOW 1501
POSITION 204
POSITION 203
UPDATE 203 3000
POSITION 203
stdout 
204
203
201 202 
203 
3
1
1
4
1
https://ideone.com/B7pEsN
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!