Árvore B
Publicado por Danilo Azevedo (última atualização em 21/07/2014)
[ Hits: 18.930 ]
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".
/* ## 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; } //##############################################
Copia uma linha selecionada para um arquivo secundário
Contando a quantidade de palavras de um arquivo texto
Montando string de conexão para banco de dados em C# através de um arquivo xml personalizado
Nenhum comentário foi encontrado.
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
E a guerra contra bots continua
Tradução do artigo do filósofo Gottfried Wilhelm Leibniz sobre o sistema binário
Conheça o firewall OpenGFW, uma implementação do (Great Firewall of China).
Instalando o FreeOffice no LMDE 6
Anki: Remover Tags de Estilo HTML de Todas as Cartas
Colocando uma opção de redimensionamento de imagem no menu de contexto do KDE
Não consigo acessar os modos de desempenho (2)
Ubuntu — tentando iniciar o windows? (0)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba