fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4. #include <math.h>
  5.  
  6. struct nod
  7. {
  8.     void *info;
  9.     struct nod *ant, *prox;
  10. };
  11. typedef struct nod Nod;
  12.  
  13. struct listad
  14. {
  15.     Nod *ini;
  16.     Nod *fim;
  17. };
  18. typedef struct listad Listad;
  19.  
  20. struct pagina
  21. {
  22.     bool folha;
  23.     int qtdeChaves;
  24.     struct pagina *pai;
  25.     Listad *listaChaves;
  26.     struct pagina *direita;
  27. };
  28.  
  29. struct chave
  30. {
  31.     int valorChave;
  32.     struct pagina *filho;
  33. };
  34.  
  35. struct arvoreb
  36. {
  37.     struct pagina *raiz;
  38.     int ordem;
  39.     int altura;
  40. };
  41.  
  42. typedef struct pagina Pagina;
  43. typedef struct chave Chave;
  44. typedef struct arvoreb Arvoreb;
  45.  
  46. Listad *cria_listad()
  47. {
  48.  
  49.     Listad *L = (Listad *)malloc(sizeof(Listad));
  50.     L->fim = L->ini = NULL;
  51.     return L;
  52. }
  53.  
  54. Nod *cria_nod(void *info)
  55. {
  56.     Nod *novo = (Nod *)malloc(sizeof(Nod));
  57.     novo->ant = novo->prox = NULL;
  58.     novo->info = info;
  59.     return novo;
  60. }
  61.  
  62. Listad *insere_inicio_listad(Listad *L, void *info)
  63. {
  64.     Nod *novo = cria_nod(info);
  65.  
  66.     if (L == NULL)
  67.     {
  68.         L = cria_listad();
  69.         L->ini = L->fim = novo;
  70.     }
  71.     else
  72.     {
  73.         if (L->ini == NULL)
  74.             L->ini = L->fim = novo;
  75.         else
  76.         {
  77.             novo->prox = L->ini;
  78.             L->ini->ant = novo;
  79.             L->ini = novo;
  80.         }
  81.     }
  82.     return L;
  83. }
  84.  
  85. Listad *insere_fim_listad(Listad *L, void *info)
  86. {
  87.     Nod *novo = cria_nod(info);
  88.  
  89.     if (L == NULL)
  90.     {
  91.         L = cria_listad();
  92.         L->ini = L->fim = novo;
  93.     }
  94.     else
  95.     {
  96.         if (L->ini == NULL)
  97.             L->ini = L->fim = novo;
  98.         else
  99.         {
  100.             novo->ant = L->fim;
  101.             L->fim->prox = novo;
  102.             L->fim = novo;
  103.         }
  104.     }
  105.     return L;
  106. }
  107.  
  108. Nod *remove_inicio_listad(Listad *L)
  109. {
  110.     Nod *aux = NULL;
  111.     if (L != NULL && L->fim != NULL) // caso haja elemento
  112.     {
  113.         aux = L->ini;
  114.         if (L->ini == L->fim)
  115.         {
  116.             L->ini = L->fim = NULL;
  117.         }
  118.         else
  119.         {
  120.             L->ini = L->ini->prox;
  121.             L->ini->ant = NULL;
  122.         }
  123.     }
  124.     return aux;
  125. }
  126.  
  127. Nod *remove_fim_listad(Listad *L)
  128. {
  129.     Nod *aux = NULL;
  130.     if (L != NULL && L->fim != NULL) // caso haja elemento
  131.     {
  132.         aux = L->fim;
  133.         if (L->ini == L->fim)
  134.         {
  135.             L->ini = L->fim = NULL;
  136.         }
  137.         else
  138.         {
  139.             L->fim = L->fim->ant;
  140.             L->fim->prox = NULL;
  141.         }
  142.     }
  143.     return aux;
  144. }
  145.  
  146. Listad *libera_listad(Listad *L)
  147. {
  148.     Nod *aux;
  149.     while (L->ini != NULL)
  150.     {
  151.         aux = L->ini;
  152.         L->ini = L->ini->prox;
  153.         free(aux);
  154.     }
  155.     L->fim = NULL;
  156.     free(L);
  157.     return NULL;
  158. }
  159.  
  160. Listad *divide_lista(Listad *L, int qtde)
  161. {
  162.     Listad *nova_lista = cria_listad();
  163.     Nod *aux;
  164.     int i;
  165.     for (i = 0, aux = L->ini;
  166.          i < qtde;
  167.          i++, aux = aux->prox)
  168.         ;
  169.  
  170.     nova_lista->ini = aux;
  171.     nova_lista->fim = L->fim;
  172.     L->fim = aux->ant;
  173.  
  174.     aux->ant = NULL;
  175.     L->fim->prox = NULL;
  176.  
  177.     return nova_lista;
  178. }
  179.  
  180. Arvoreb *cria_arvoreb(int ordem)
  181. {
  182.     Arvoreb *T = malloc(sizeof(Arvoreb));
  183.     T->altura = 0;
  184.     T->ordem = ordem;
  185.     T->raiz = NULL;
  186.     return T;
  187. }
  188.  
  189. Pagina *cria_pagina()
  190. {
  191.     Pagina *nova = malloc(sizeof(Pagina));
  192.     nova->folha = true; // se é ou não uma folha
  193.     nova->qtdeChaves = 0;
  194.     nova->pai = NULL;
  195.     nova->direita = NULL;
  196.     nova->listaChaves = cria_listad();
  197.     return nova;
  198. }
  199.  
  200. Chave *cria_chave(int nova_chave)
  201. {
  202.     Chave *nova = malloc(sizeof(Chave));
  203.     nova->filho = NULL;
  204.     nova->valorChave = nova_chave;
  205.     return nova;
  206. }
  207.  
  208. Chave *getChave(Nod *aux)
  209. {
  210.     return (aux->info);
  211. }
  212.  
  213. Pagina *encontra_folha(Arvoreb *T, int nova_chave)
  214. {
  215.     Pagina *aux_pg = T->raiz;
  216.     Nod *aux_no = NULL;
  217.  
  218.     while (!aux_pg->folha) //(aux_pg->folha == 0) //nao é folha
  219.     {
  220.         aux_no = aux_pg->listaChaves->ini;
  221.         while (aux_no != NULL && nova_chave > getChave(aux_no)->valorChave)
  222.             aux_no = aux_no->prox;
  223.  
  224.         if (aux_no == NULL)
  225.             aux_pg = aux_pg->direita;
  226.         else
  227.             aux_pg = getChave(aux_no)->filho;
  228.     }
  229.     return aux_pg;
  230. }
  231.  
  232. Pagina *insere_chave_na_pagina(Pagina *pagina1, Chave *nova_chave)
  233. {
  234.  
  235.     if (pagina1 == NULL)
  236.     {
  237.         pagina1 = cria_pagina();
  238.     }
  239.     Nod *aux = pagina1->listaChaves->ini;
  240.  
  241.     if (aux == NULL)
  242.     {
  243.         pagina1->listaChaves = insere_inicio_listad(pagina1->listaChaves, nova_chave);
  244.     }
  245.     else
  246.     {
  247.         if (nova_chave->valorChave < getChave(aux)->valorChave)
  248.         {
  249.             pagina1->listaChaves = insere_inicio_listad(pagina1->listaChaves, nova_chave);
  250.         }
  251.         else if (nova_chave->valorChave > getChave(pagina1->listaChaves->fim)->valorChave)
  252.         {
  253.             pagina1->listaChaves = insere_fim_listad(pagina1->listaChaves, nova_chave);
  254.         }
  255.         else // inserir ordenado
  256.         {
  257.             while (nova_chave->valorChave > getChave(aux)->valorChave)
  258.             {
  259.                 aux = aux->prox;
  260.             }
  261.             Nod *novo_no = cria_nod(nova_chave);
  262.             novo_no->prox = aux;
  263.             novo_no->ant = aux->ant;
  264.             aux->ant->prox = novo_no;
  265.             aux->ant = novo_no;
  266.         }
  267.     }
  268.     printf("qnt de chaves: %d\n", pagina1->qtdeChaves);
  269.     pagina1->qtdeChaves++;
  270.     return pagina1;
  271. }
  272.  
  273. Pagina *cria_nova_raiz(Chave *chave_subir, Pagina *filho_esq, Pagina *filho_dir)
  274. {
  275.     Pagina *nova_raiz = cria_pagina();
  276.     nova_raiz = insere_chave_na_pagina(nova_raiz, chave_subir);
  277.     chave_subir->filho = filho_esq;
  278.     nova_raiz->direita = filho_dir;
  279.     filho_dir->pai = filho_esq->pai = nova_raiz;
  280.     nova_raiz->folha = false;
  281.     return nova_raiz;
  282. }
  283.  
  284. Pagina *divide_pagina(Pagina *pagina_inserir)
  285. {
  286.     Nod *aux_no;
  287.     Pagina *pai;
  288.     Pagina *nova_pagina = cria_pagina();
  289.     int qtde_chaves_lista = ceil(pagina_inserir->qtdeChaves / 2.0);
  290.  
  291.     // atualizar a nova pagina
  292.     nova_pagina->listaChaves = divide_lista(pagina_inserir->listaChaves, qtde_chaves_lista);
  293.     nova_pagina->folha = pagina_inserir->folha;
  294.     nova_pagina->qtdeChaves = floor(pagina_inserir->qtdeChaves / 2.0);
  295.     nova_pagina->direita = pagina_inserir->direita;
  296.     nova_pagina->pai = pagina_inserir->pai;
  297.  
  298.     // atualizar pagina dividida
  299.     pagina_inserir->qtdeChaves = qtde_chaves_lista;
  300.  
  301.     pai = pagina_inserir->pai;
  302.  
  303.     // quem vai apontar para a nova página
  304.     if (pagina_inserir->pai != NULL)
  305.     {
  306.         aux_no = pai->listaChaves->ini;
  307.         while (aux_no != NULL && getChave(aux_no)->filho != pagina_inserir)
  308.             aux_no = aux_no->prox;
  309.         if (aux_no == NULL)
  310.             pai->direita = nova_pagina;
  311.         else
  312.             getChave(aux_no)->filho = nova_pagina;
  313.     }
  314.  
  315.     if (!nova_pagina->folha)
  316.     {
  317.         aux_no = nova_pagina->listaChaves->ini;
  318.         while (aux_no != NULL)
  319.         {
  320.             getChave(aux_no)->filho->pai = nova_pagina;
  321.             aux_no = aux_no->prox;
  322.         }
  323.  
  324.         nova_pagina->direita->pai = nova_pagina;
  325.         // a direita da página que foi dividida
  326.         // precisa apontar para o mesmo lugar que
  327.         // a chave anterior a ela aponta
  328.         pagina_inserir->direita = getChave(pagina_inserir->listaChaves->fim)->filho;
  329.     }
  330.  
  331.     // chave a subir, mudar filho
  332.     getChave(pagina_inserir->listaChaves->fim)->filho = pagina_inserir;
  333.  
  334.     return nova_pagina;
  335. }
  336.  
  337. Arvoreb *insere_arvoreb(Arvoreb *T, int nova_ch)
  338. {
  339.     bool tem_chave_para_inserir = true;
  340.     Pagina *nova_pagina;
  341.     Chave *nova_chave = cria_chave(nova_ch), *chave_subir;
  342.     Nod *aux;
  343.     int qnt_divisao = 0;
  344.     // arvore for vazia
  345.     if (T == NULL || T->raiz == NULL)
  346.     {
  347.         T = cria_arvoreb(T->ordem);
  348.         T->raiz = insere_chave_na_pagina(T->raiz, nova_chave);
  349.     }
  350.     else
  351.     {
  352.         Pagina *pagina_inserir = encontra_folha(T, nova_ch);
  353.         while (tem_chave_para_inserir)
  354.         {
  355.             pagina_inserir = insere_chave_na_pagina(pagina_inserir, nova_chave);
  356.             // Chave *ch_subir = chave que vai subir
  357.  
  358.             if (pagina_inserir->qtdeChaves < T->ordem) // nao estorou
  359.             {
  360.                 tem_chave_para_inserir = false;
  361.             }
  362.             else // estorou
  363.             {
  364.  
  365.                 nova_pagina = divide_pagina(pagina_inserir);
  366.                 aux = remove_fim_listad(pagina_inserir->listaChaves);
  367.                 pagina_inserir->qtdeChaves--;
  368.                 chave_subir = aux->info;
  369.                 free(aux);
  370.  
  371.                 if (pagina_inserir->pai == NULL) // folha é a raiz
  372.                 {
  373.                     T->raiz = cria_nova_raiz(chave_subir, pagina_inserir, nova_pagina);
  374.                     tem_chave_para_inserir = false;
  375.                 }
  376.                 else
  377.                 {
  378.                     pagina_inserir = pagina_inserir->pai;
  379.                     nova_chave = chave_subir;
  380.                 }
  381.                 qnt_divisao++;
  382.             }
  383.         }
  384.     }
  385.  
  386.     return T;
  387. }
  388.  
  389. void em_ordem(Pagina *raiz)
  390. {
  391.     Nod *aux;
  392.     if (raiz != NULL)
  393.     {
  394.         aux = raiz->listaChaves->ini;
  395.         while (aux != NULL)
  396.         {
  397.             em_ordem(getChave(aux)->filho);
  398.             printf("%d ", getChave(aux)->valorChave);
  399.             aux = aux->prox;
  400.         }
  401.         em_ordem(raiz->direita);
  402.     }
  403. }
  404.  
  405. void libera_arvore(Pagina *raiz)
  406. {
  407.     Nod *aux;
  408.     if (raiz != NULL)
  409.     {
  410.         aux = raiz->listaChaves->ini;
  411.         while (raiz->listaChaves->ini != NULL)
  412.         {
  413.             em_ordem(getChave(aux)->filho);
  414.             aux = raiz->listaChaves->ini;
  415.             raiz->listaChaves->ini = raiz->listaChaves->ini->prox;
  416.             free(aux->info);
  417.             free(aux);
  418.         }
  419.         raiz->listaChaves->fim = NULL;
  420.         free(raiz->listaChaves);
  421.         em_ordem(raiz->direita);
  422.         free(raiz);
  423.     }
  424. }
  425.  
  426. int main()
  427. {
  428.     int vet[] =
  429.         {
  430.             50, 30, 40, 44, 88, 95,
  431.             25, 91, 31, 52, 20, 60,
  432.             70, 74, 78, 79, 22, 28,
  433.             33, 39, 98, 85, 86, 87,
  434.             90, 92, 93, 94, 35, 32,
  435.             84, 99, 95, 10, 05, 02};
  436.  
  437.     int i = 0;
  438.     int tam = 35;
  439.     Arvoreb *T = cria_arvoreb(4);
  440.  
  441.     for (i = 0; i < tam; i++)
  442.     {
  443.         T = insere_arvoreb(T, vet[i]);
  444.     }
  445.     printf("");
  446.     T = insere_arvoreb(T, vet[i]);
  447.     printf("");
  448.     em_ordem(T->raiz);
  449.  
  450.     return 0;
  451. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
qnt de chaves: 0
qnt de chaves: 1
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 0
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 1
qnt de chaves: 1
qnt de chaves: 2
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 3
qnt de chaves: 0
qnt de chaves: 1
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 2
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 3
qnt de chaves: 1
qnt de chaves: 1
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 1
qnt de chaves: 2
qnt de chaves: 2
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 2
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 3
qnt de chaves: 2
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 2
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 2
qnt de chaves: 1
qnt de chaves: 3
qnt de chaves: 3
qnt de chaves: 3
qnt de chaves: 0
qnt de chaves: 3
qnt de chaves: 2
qnt de chaves: 1
qnt de chaves: 2
qnt de chaves: 3
qnt de chaves: 3
qnt de chaves: 1
qnt de chaves: 1
2 5 10 20 22 25 28 30 31 32 33 35 39 40 44 50 52 60 70 74 78 79 84 85 86 87 88 90 91 92 93 94 95 95 98 99
https://ideone.com/acWU8S
language:
C (gcc 8.3)
created:
11 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!