Árvore B [C/C++]

Árvore B

Publicado por Danilo Azevedo (última atualização em 21/07/2014)

[ Hits: 20.591 ]

Download BtreeDAS.c.zip

1 0

Denuncie Favoritos Indicar
Implementação de uma árvore B. Conforme definição, cada nó da árvore conterá, com exceção da raiz, no mínimo "d" registros e no máximo "2d" registros, onde "d" é a ordem da árvore. O código trata-se da adaptação de alguns exemplos de livros de estrutura de dados e organização de arquivos.

Para começar a inserção entre com a letra "i" e na linha seguinte uma chave (um número maior que 0), na linha seguinte um nome e na linha seguinte uma idade.

Para consultar ou remover registros entre:
- consultar - "c", na linha seguinte a chave.
- remover - "r", na linha seguinte a chave.

Para imprimir a estrutura entre com a letra "p" ou "o".
Esconder código-fonte
/*
## Universidade Federal da Bahia
## Docente: Danilo Azevedo
## Bacharelado em Ciencia da Computacao - Estrutura de Dados II

chaves testadas: 20,40,10,30,15,35,7,26,18,22,
5,42,13,46,27,8,32,38,24,45,25

 */

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define ORDEM 2
#define namefile "_arquivo.dat"


int cont = -1, count = 0;

typedef struct
{
  int chave;
  char nome[20];
  int idade;
  int ApPage[2];
  int rank;
} Registro;

typedef struct Pagina_str *Apontador;
typedef struct Pagina_str
{
  int n;
  int pageNum;
  int num;
  Registro r[2*ORDEM];
  Apontador p[2*ORDEM+1];
} Pagina;

struct Node{
    Registro info;
    struct Node *prox;
};
typedef struct Node node;

//##########################################################
void Antecessor(Apontador Ap, int Ind, Apontador ApPai, int *Diminuiu);
void Busca(Registro Reg, Apontador Ap);void em_ordem(Apontador raiz);
void buscainFile(Registro Reg, Apontador pagina);int isleaf(Apontador a);
int file_exists(const char *filename);void Insere(Registro Reg, Apontador *Ap);
void InsereNaPagina(Apontador Ap, Registro Reg, Apontador ApDir);
void Ins(Registro Reg, Apontador Ap, int *Cresceu, Registro *RegRetorno, Apontador *ApRetorno);
int Imprime2(Apontador p, int Nivel, int aux, int n);int Imprime(Apontador p, int N, int aux, int n);
void InsertPosFile(Registro Reg, Apontador *Ap);node *busca(Registro info, node *LISTA);
void InsPosFile(Registro Reg, Apontador Ap, int *Cresceu, Registro *RegRetorno, Apontador *ApRetorno);
void pos_ordem(Apontador raiz);void Retira(int Ch, Apontador *Ap);void Ret(int Ch, Apontador *Ap, int *Diminuiu);
void Reconstitui(Apontador ApPag, Apontador ApPai, int PosPai, int *Diminuiu);
void saveAux(Apontador p, int Nivel);void salvar(Apontador pagina, Registro Reg[]);
void recuperarReg(Apontador *arv, node *LISTA);void insereInicio(Registro info, node *LISTA);
void execut(Registro info, node *LISTA);void exibe(node *LISTA);

typedef Apontador TipoDicionario;
void Inicializa(TipoDicionario *Dicionario)
{
  *Dicionario = NULL;
}  /* Inicializa a estrutura */

void inicia(node *LISTA)
{
    LISTA->prox = NULL;
}

//############################### Estrutura 1 Btree

void Antecessor(Apontador Ap, int Ind, Apontador ApPai, int *Diminuiu)
{
  if (ApPai->p[ApPai->n] != NULL)
  {
    Antecessor(Ap, Ind, ApPai->p[ApPai->n], Diminuiu);
    if (*Diminuiu)
      Reconstitui(ApPai->p[ApPai->n], ApPai, ApPai->n, Diminuiu);
    return;
  }
  Ap->r[Ind - 1] = ApPai->r[ApPai->n - 1];
  ApPai->n--;
  *Diminuiu = ApPai->n < ORDEM;
}  /* Antecessor */

void Busca(Registro Reg, Apontador Ap)
{
  int i;

  if (Ap == NULL) //
  {
    printf("chave nao encontrada: %d\n", Reg.chave);
    return;
  }
  i = 1;
  while (i < Ap->n && Reg.chave > Ap->r[i - 1].chave)
    i++;
  if (Reg.chave == Ap->r[i - 1].chave)
  {
    printf("chave: %d \n", Reg.chave);
    buscainFile(Ap->r[i-1],Ap);
    return;
  }
  if (Reg.chave < Ap->r[i - 1].chave)
    Busca(Reg, Ap->p[i-1]);
  else
    Busca(Reg, Ap->p[i]);
}

void buscainFile(Registro Reg, Apontador pagina)
{
    Registro reg[2*ORDEM];
    int i;
    FILE *arq = fopen(namefile,"rb");
    if (arq == NULL)
    exit(1);
    fseek(arq, pagina->pageNum*(2*ORDEM*sizeof(Registro)), SEEK_SET);
    fread(reg, (2*ORDEM*sizeof(Registro)),1,arq);
    fclose(arq);
    for(i = 0; i < 2*ORDEM; i++){
        if (Reg.chave == reg[i].chave)
        printf("%s%d\n",reg[i].nome,reg[i].idade);
            }
    }

void em_ordem(Apontador raiz)
{
  int i;
  if (raiz != NULL)
   {
     for (i = 0; i < raiz->n; i++)
      {
        em_ordem(raiz->p[i]);
        printf("%d ", raiz->r[i].chave);
        printf("\n");
      }
     em_ordem(raiz->p[i]);
      }
}

int file_exists(const char *filename)
{
  FILE *arquivo;

  if((arquivo = fopen(filename, "rb")))
  {
    fclose(arquivo);
    return 1;
  }
  return 0;
}

int isleaf(Apontador a)
{
    if (a->p[0] == NULL)
    return 1;
    else
    return 0;
}

void InsereNaPagina(Apontador Ap, Registro Reg, Apontador ApDir)
{

  int k;
  int NaoAchouPosicao;

  k = Ap->n;
  NaoAchouPosicao = k > 0;
  while (NaoAchouPosicao)
  {
    if (Reg.chave >= Ap->r[k - 1].chave)
    {
      NaoAchouPosicao = 0;
      break;
    }

    Ap->r[k] = Ap->r[k - 1];

    Ap->p[k + 1] = Ap->p[k];

    k--;
    if (k < 1)
      NaoAchouPosicao = 0;
  }
  Ap->r[k] = Reg;
  Ap->p[k + 1] = ApDir;
  Ap->n++;
}

void Ins(Registro Reg, Apontador Ap, int *Cresceu, Registro *RegRetorno, Apontador *ApRetorno)
{
  Apontador ApTemp;
  Registro Aux;
  int i, j;

  if (Ap == NULL)
  {
    *Cresceu = 1;
    *RegRetorno = Reg;
    *ApRetorno = NULL;
    return;
  }
  i = 1;
  while (i < Ap->n && Reg.chave > Ap->r[i - 1].chave)
    i++;
  if (Reg.chave == Ap->r[i - 1].chave)
  {
    printf("chave ja existente: %d \n", Reg.chave);
    *Cresceu = 0;
    return;
  }
  if (Reg.chave < Ap->r[i - 1].chave)
    Ins(Reg, Ap->p[i-1], Cresceu, RegRetorno, ApRetorno);
  else
    Ins(Reg, Ap->p[i], Cresceu, RegRetorno, ApRetorno);
  if (!*Cresceu)
    return;
  if (Ap->n < 2*ORDEM)
  {  /* Verificando se a pagina tem espaco */
    InsereNaPagina(Ap, *RegRetorno, *ApRetorno);
    *Cresceu = 0;
    return;
  }
  /* Split: Pagina tem que ser dividida */
  ApTemp = (Apontador) malloc(sizeof(Pagina));
  ApTemp->n = 0;
  ApTemp->p[0] = NULL;
  cont++;
  ApTemp->pageNum = cont;

  if (i <= ORDEM + 1)
  {
    InsereNaPagina(ApTemp, Ap->r[2*ORDEM - 1], Ap->p[2*ORDEM]);
    Ap->n--;
    InsereNaPagina(Ap, *RegRetorno, *ApRetorno);
  }
  else{
    InsereNaPagina(ApTemp, *RegRetorno, *ApRetorno);
    }
  for (j = ORDEM + 2; j <= 2*ORDEM; j++)
    InsereNaPagina(ApTemp, Ap->r[j - 1], Ap->p[j]);


  Ap->n = ORDEM;
  ApTemp->p[0] = Ap->p[ORDEM + 1];
  *RegRetorno = Ap->r[ORDEM];
  *ApRetorno = ApTemp;
 for (j = ORDEM; j < Ap->n+2; j++){
    Aux.chave = 0;
    Aux.rank = 0;
    Ap->r[j] = Aux;
        }
}  /*Ins*/

void Insere(Registro Reg, Apontador *Ap)
{
  int Cresceu;
  Registro RegRetorno;
  Apontador ApRetorno;
  Apontador ApTemp;

  Ins(Reg, *Ap, &Cresceu, &RegRetorno, &ApRetorno);
  if (Cresceu) { /* Se arvore cresce na altura pela raiz */
    ApTemp = (Apontador) malloc(sizeof(Pagina));
    ApTemp->n = 1;
    ApTemp->r[0] = RegRetorno;
    ApTemp->p[1] = ApRetorno;
    cont++;
    ApTemp->pageNum = cont;
    ApTemp->p[0] = *Ap;
    *Ap = ApTemp;
    //save in file
  }
  saveAux(*Ap, 2*ORDEM);
}  /*Insercao*/

int Imprime2(Apontador p, int Nivel, int aux, int n)
{
  int i;

  if (p == NULL)
    return 0;
  if(Nivel == aux){
      n++;
    printf("No: %d : ",p->pageNum);
  for (i = 0; i < p->n; i++){
      if (p->p[i] !=NULL)
    printf("Apontador: %d ", p->p[i]->pageNum);
    else
    printf("Apontador: null ");
    printf("chave: %d ", p->r[i].chave);
   }
   printf("\n");
   return n;
 }else{
    aux++;
     for (i = 0; i <= p->n; i++)
     Imprime2(p->p[i], Nivel, aux, n);
     }
    return 0;
}

int Imprime(Apontador p, int N, int aux, int n)
{
  int i;

  if (p == NULL)
    return 0;
  if(p->pageNum != aux){
    p->num = N;
    aux = p->pageNum;
    return aux;
 }else{
    aux++;
     for (i = 0; i <= p->n; i++)
     Imprime(p->p[i], N, aux, n);
     }
     return 0;
}

void InsertPosFile(Registro Reg, Apontador *Ap)
{
  int Cresceu;
  Registro RegRetorno;
  Apontador ApRetorno;
  Apontador ApTemp;

  InsPosFile(Reg, *Ap, &Cresceu, &RegRetorno, &ApRetorno);
  if (Cresceu) { /* Se arvore cresce na altura pela raiz */
    ApTemp = (Apontador) malloc(sizeof(Pagina));
    ApTemp->n = 1;
    ApTemp->r[0] = RegRetorno;
    ApTemp->p[1] = ApRetorno;
    cont++;
    ApTemp->pageNum = cont;
    ApTemp->p[0] = *Ap;
    *Ap = ApTemp;
  }
}

void InsPosFile(Registro Reg, Apontador Ap, int *Cresceu, Registro *RegRetorno, Apontador *ApRetorno)
{
  Apontador ApTemp;
  Registro Aux;
  int i, j;

  if (Ap == NULL) //
  {
    *Cresceu = 1;
    *RegRetorno = Reg;
    *ApRetorno = NULL;
    return;
  }
  i = 1;
  while (i < Ap->n && Reg.chave > Ap->r[i - 1].chave)
    i++;
  if (Reg.chave == Ap->r[i - 1].chave)
  {
    //printf("chave ja existente: %d \n", Reg.chave);
    *Cresceu = 0;
    return;
  }
  if (Reg.chave < Ap->r[i - 1].chave)
    InsPosFile(Reg, Ap->p[i-1], Cresceu, RegRetorno, ApRetorno);
  else
    InsPosFile(Reg, Ap->p[i], Cresceu, RegRetorno, ApRetorno);
  if (!*Cresceu)
    return;
  if (Ap->n < 2*ORDEM)
  {  /* Verificando se a pagina tem espaco */
    InsereNaPagina(Ap, *RegRetorno, *ApRetorno);
    *Cresceu = 0;
    return;
  }
  /* Split: Pagina tem que ser dividida */
  ApTemp = (Apontador) malloc(sizeof(Pagina));
  ApTemp->n = 0;
  ApTemp->p[0] = NULL;
  cont++;
  ApTemp->pageNum = cont;

  if (i <= ORDEM + 1)
  {
    InsereNaPagina(ApTemp, Ap->r[2*ORDEM - 1], Ap->p[2*ORDEM]);
    Ap->n--;
    InsereNaPagina(Ap, *RegRetorno, *ApRetorno);
  }
  else{
    InsereNaPagina(ApTemp, *RegRetorno, *ApRetorno);
    }
  for (j = ORDEM + 2; j <= 2*ORDEM; j++)
    InsereNaPagina(ApTemp, Ap->r[j - 1], Ap->p[j]);


  Ap->n = ORDEM;
  ApTemp->p[0] = Ap->p[ORDEM + 1];
  *RegRetorno = Ap->r[ORDEM];
  *ApRetorno = ApTemp;
 for (j = ORDEM; j < Ap->n+2; j++){
    Aux.chave = 0;
    Aux.rank = 0;
    Ap->r[j] = Aux;
    }
}

void pos_ordem(Apontador raiz)
{
  int i;
 if (isleaf(raiz)){
    for (i = raiz->n-1; i >=0; i--){
        printf("%d\n", raiz->r[i].chave);

     }
  }
  else{
    pos_ordem(raiz->p[raiz->n]);
    for (i = raiz->n-1; i >=0; i--){
        printf("%d\n", raiz->r[i].chave);
    pos_ordem(raiz->p[i]);
        }
    }
}

void Pesquisa(Registro *x, Apontador Ap)
{
  int i;

  if (Ap == NULL)
  {
    //printf("Erro: Registro nao existe\n");

    return;
  }
  i = 1;
  while (i < Ap->n && x->chave > Ap->r[i - 1].chave)
    i++;
  if (x->chave == Ap->r[i - 1].chave)
  {
    *x = Ap->r[i - 1];
    return;
  }
  if (x->chave < Ap->r[i - 1].chave)
    Pesquisa(x, Ap->p[i - 1]);
  else
    Pesquisa(x, Ap->p[i]);
} /* Pesquisa */

void Reconstitui(Apontador ApPag, Apontador ApPai, int PosPai, int *Diminuiu)
{
  Apontador Aux;
  int DispAux, j;

  if (PosPai < ApPai->n) {  /* Aux = Pagina a direita de ApPag */
    Aux = ApPai->p[PosPai + 1];
    DispAux = (Aux->n - ORDEM + 1) / 2;
    ApPag->r[ApPag->n] = ApPai->r[PosPai];
    ApPag->p[ApPag->n + 1] = Aux->p[0];
    ApPag->n++;
    if (DispAux > 0) {  /* Existe folga: transfere de Aux para ApPag */
      for (j = 1; j < DispAux; j++)
        InsereNaPagina(ApPag, Aux->r[j - 1], Aux->p[j]);
      ApPai->r[PosPai] = Aux->r[DispAux - 1];
      Aux->n -= DispAux;
      for (j = 0; j < Aux->n; j++)
        Aux->r[j] = Aux->r[j + DispAux];
      for (j = 0; j <= Aux->n; j++)
        Aux->p[j] = Aux->p[j + DispAux];
      *Diminuiu = 0;
    }
    else
    { /* Fusao: intercala Aux em ApPag e libera Aux */
      for (j = 1; j <= ORDEM; j++)
        InsereNaPagina(ApPag, Aux->r[j - 1], Aux->p[j]);
      free(Aux);
      for (j = PosPai + 1; j < ApPai->n; j++)
      {   /* Preenche vazio em ApPai */
        ApPai->r[j - 1] = ApPai->r[j];
        ApPai->p[j] = ApPai->p[j + 1];
      }
      ApPai->n--;
      if (ApPai->n >= ORDEM)
        *Diminuiu = 0;
    }
  }
  else
  { /* Aux = Pagina a esquerda de ApPag */
    Aux = ApPai->p[PosPai - 1];
    DispAux = (Aux->n - ORDEM + 1) / 2;
    for (j = ApPag->n; j >= 1; j--)
      ApPag->r[j] = ApPag->r[j - 1];
    ApPag->r[0] = ApPai->r[PosPai - 1];
    for (j = ApPag->n; j >= 0; j--)
      ApPag->p[j + 1] = ApPag->p[j];
    ApPag->n++;
    if (DispAux > 0) {  /* Existe folga: transfere de Aux para ApPag */
      for (j = 1; j < DispAux; j++)
        InsereNaPagina(ApPag, Aux->r[Aux->n - j], Aux->p[Aux->n - j + 1]);
      ApPag->p[0] = Aux->p[Aux->n - DispAux + 1];
      ApPai->r[PosPai - 1] = Aux->r[Aux->n - DispAux];
      Aux->n -= DispAux;
      *Diminuiu = 0;
    }
    else
    {  /* Fusao: intercala ApPag em Aux e libera ApPag */
      for (j = 1; j <= ORDEM; j++)
        InsereNaPagina(Aux, ApPag->r[j - 1], ApPag->p[j]);
      free(ApPag);
      ApPai->n--;
      if (ApPai->n >= ORDEM)
        *Diminuiu = 0;
    }
  }
}  /* Reconstitui */

void Ret(int Ch, Apontador *Ap, int *Diminuiu)
{
  int Ind, j;
  Apontador WITH;
  Registro Reg;

  if (*Ap == NULL)
  {
    printf("chave nao encontrada: %i\n", Ch);
    *Diminuiu = 0;
    return;
  }
  WITH = *Ap;
  Ind = 1;
  while (Ind < WITH->n && Ch > WITH->r[Ind - 1].chave)
    Ind++;
  if (Ch == WITH->r[Ind - 1].chave)
  {
    Reg.chave = 0;
    Reg.rank = 0;
    WITH->r[Ind -1] = Reg;
    if (WITH->p[Ind - 1] == NULL) {  /* Pagina folha */
      WITH->n--;
      *Diminuiu = WITH->n < ORDEM;
      for (j = Ind; j <= WITH->n; j++)
      {
        WITH->r[j - 1] = WITH->r[j];
        WITH->p[j] = WITH->p[j + 1];
      }
      return;
    }
    Antecessor(*Ap, Ind, WITH->p[Ind - 1], Diminuiu);
    if (*Diminuiu)
      Reconstitui(WITH->p[Ind - 1], *Ap, Ind - 1, Diminuiu);
    return;
  }
  if (Ch > WITH->r[Ind - 1].chave)
    Ind++;
  Ret(Ch, &WITH->p[Ind - 1], Diminuiu);
  if (*Diminuiu)
    Reconstitui(WITH->p[Ind - 1], *Ap, Ind - 1, Diminuiu);
}  /* Ret */

void Retira(int Ch, Apontador *Ap)
{
  int Diminuiu;
  Apontador Aux;

  Ret(Ch, Ap, &Diminuiu);
  if (Diminuiu && (*Ap)->n == 0) { /* Arvore diminui na altura */
    Aux = *Ap;
    *Ap = Aux->p[0];
    free(Aux);

  }

}  /* Retira */

void recuperarReg(Apontador *arv, node *LISTA)
{

    FILE* arq;
    Registro Reg[2*ORDEM];
    node *tmp;
    int i=0,j=0, tam;
        arq = fopen(namefile,"rb");
        if (arq == NULL)
            exit(1);
       fseek(arq, 0, SEEK_END);
       tam = ftell(arq);
       rewind(arq);
       fclose(arq);

       arq = fopen(namefile,"rb");
        if (arq == NULL)
            exit(1);
        while (j*(2*ORDEM*sizeof(Registro)) < tam){
            fseek(arq, j*(2*ORDEM*sizeof(Registro)), SEEK_SET);
            fread(Reg, 2*ORDEM*sizeof(Registro),1,arq);

        for(i = 0; i < 2*ORDEM; i++){
           if (Reg[i].chave > 0)
           execut(Reg[i], LISTA);
        }
    j++;
    }
    fclose(arq);
    tmp = LISTA->prox;
    while( tmp != NULL){
        InsertPosFile(tmp->info, arv);
        tmp = tmp->prox;
    }
    free(tmp);
    free(LISTA);
    //Imprime(*arv, 2*ORDEM, 0);
    }

void saveAux(Apontador p, int Nivel)
{
  int i,j;

  if (p == NULL)
    return;
  for (i = 0; i < p->n; i++)
    salvar(p, p->r);
  for (j = 0; j <= p->n; j++)
    saveAux(p->p[j], Nivel + 1);
}

void salvar(Apontador pagina, Registro Reg[])
{

    FILE* arq;
    if (!file_exists(namefile)){
        arq = fopen(namefile,"wb");
        if (arq == NULL)
            exit(1);
        fseek(arq, pagina->pageNum*(2*ORDEM*sizeof(Registro)), SEEK_SET);
        fwrite(Reg,(2*ORDEM*sizeof(Registro)),1,arq);
        fclose(arq);
    }

    else{
        arq = fopen(namefile,"r+b");
        if (arq == NULL)
            exit(1);
        fseek(arq, pagina->pageNum*(2*ORDEM*sizeof(Registro)), SEEK_SET);
        fwrite(Reg, (2*ORDEM*sizeof(Registro)),1,arq);
        fclose(arq);
        }
    }

//############################### //Estrutura 1 Btree

//############################### //Estrutura 2 lista encadeada
void insereInicio(Registro info, node *LISTA)
{
    node *novo=(node *) malloc(sizeof(node));
    node *tmp = busca(info, LISTA);
    if(LISTA->prox == NULL){
        novo->info = info;
        novo->prox = LISTA->prox;
        LISTA->prox = novo;
    }else{
    novo->prox = tmp->prox;
    novo->info = info;
    tmp->prox = novo;
}
//exibe(LISTA);
}

node *busca(Registro info, node *LISTA)
{
        node *atual,*antNode;
        atual = LISTA->prox;
        antNode = LISTA;
        while(atual != NULL && info.rank > atual->info.rank){
            antNode = atual;
            atual = atual->prox;
        }
        return antNode;
    }

void exibe(node *LISTA)
{
    if(!LISTA){
        return ;
    }
    node *tmp;
    tmp = LISTA->prox;

    while( tmp != NULL){
        printf(" %d ", tmp->info.chave);
        tmp = tmp->prox;
    }
    printf("\n");
}

void execut(Registro info, node *LISTA)
{
    insereInicio(info, LISTA);
    }

//############################# //Estrutura 2 lista encadeada

int main()
{
  Apontador *arv;
  Registro reg;
  char tecla;
  int chave, i, num = 0;
  arv=(Apontador*) malloc(sizeof(Apontador));
  node *LISTA = (node *) malloc(sizeof(node));
  Inicializa(arv);
  inicia(LISTA);
    if (file_exists(namefile)){
        recuperarReg(arv, LISTA);
        }

  while(1)
  {
    scanf("%c", &tecla);
    if (tecla=='e')
      break;
    switch(tecla)
    {
      case 'i':
      //printf("insercao \n");
           scanf("%d", &chave);
           reg.chave = chave;
           count++;
           reg.rank = count;
           fflush(stdin);
           getchar();
           fgets(reg.nome, sizeof(reg.nome), stdin);
           scanf("%d", ®.idade);
           if (reg.chave <= 0){
               count--;
            break;
            }
            Insere(reg,arv);
      break;
      case 'r':
           scanf("%d", &chave);
           reg.chave = chave;
           Retira(reg.chave, arv);
           remove(namefile);
            saveAux(*arv,2*ORDEM);
      break;
      case 'o':
            em_ordem(*arv);
      break;
      case 'p':
      for(i=0; i < 2*ORDEM; i++){
            num = Imprime2(*arv, i, 0, num);
      }
      break;
      case 'c':
      getchar();
      scanf("%d", &chave);
      reg.chave = chave;
      Busca(reg,*arv);
      break;
    }

    fflush(stdin);
  }
  return 0;
  }

//##############################################
Scripts recomendados
Gerenciamento de alunos com dados armazenados em arquivo
Exemplo de manipulação de arquivos
Ler .conf
Leitura de arquivo texto separando as colunas
ORDENACAO PELO METODO SHELLSORT
Comentários
Nenhum comentário foi encontrado.