0
I’m having trouble with the b-tree structure, it’s misporting the node and it’s missing some keys. I honestly don’t know what I did wrong.
#include <stdio.h>
#include <stdlib.h>
#define T 2 //Constante T que determina o tamanho da Arv.B
#define MAX_CHAVES ( 2 * T - 1 ) //Maximo de registros
#define MAX_FILHOS ( 2 * T ) //Maximo de filhos
#define MIN_CHAVES ( T - 1 ) //Minimo de registros
//definicaoda estrutura 'tipoArvB'
struct estruturaArvB {
int contChaves;
long int chaves[MAX_CHAVES];
struct estruturaArvB *filhos[MAX_FILHOS];
int folha;
};
typedef struct estruturaArvB tipoArvB;
//Prototipo das funcoes
tipoArvB *alocaNovoNo ();
int buscaBinaria (tipoArvB *raiz, long int valor);
void insereChave (tipoArvB *raiz, long int valor, tipoArvB *filhoDir);
tipoArvB *insere (tipoArvB *raiz, long int valor, int *flag, long int *valorRetorno);
tipoArvB *insereArvB (tipoArvB *raiz, long int valor);
//Funcao para alocacao de um novo no (inicializando os campos)
tipoArvB *alocaNovoNo() {
tipoArvB *novoNo;
int i;
novoNo = (tipoArvB *) malloc (sizeof(tipoArvB));
novoNo->contChaves = 0;
novoNo->folha = 1;
for (i = 0; i < MAX_CHAVES; i++)
novoNo->chaves[i] = 0;
for (i = 0; i < MAX_FILHOS; i++)
novoNo->filhos[i] = NULL;
return novoNo;
}
//Funcao que executa a busca binaria no no
int buscaBinaria (tipoArvB *raiz, long int valor) {
int inicio, meio, fim;
inicio = 0;
fim = raiz->contChaves;
while (inicio < fim) {
if (inicio == fim) {
meio = inicio; //ou fim
return (meio);
} else {
meio = (inicio + (fim - inicio) / 2 );
}
if ( raiz->chaves[meio] == valor ) {
return meio;
} else {
if (valor < raiz->chaves[meio])
fim = (meio-1);
else
inicio = (meio+1);
}
}
return (meio);
}
//funcao para insercao de uma chave e o ponteiro para o filho direito em um no nao cheio
void insereChave (tipoArvB *no, long int valor, tipoArvB *filhoDir) {
int i, pos;
//Busca a posicao correta para insercao da nova chave
pos = buscaBinaria (no, valor);
i = no->contChaves;
//Executa o remanejamento dos valores para manter a ordenacao
while ( (i > pos) && (valor < no->chaves[i-1]) ) {
no->chaves[i] = no->chaves[i-1];
no->filhos[i+1] = no->filhos[i];
i--;
}
//Executa a insercao da nova chave
no->chaves[pos] = valor;
no->filhos[pos+1] = filhoDir;
no->contChaves++;
}
//funcao que busca pelo no onde deve ser inserido o valor/chave e faz a quebra do no, quando necessario
tipoArvB *insere (tipoArvB *no, long int valor, int *flag, long int *valorRetorno) {
int i, pos;
int meio;
tipoArvB *noAux, *filhoDir;
if (no == NULL) {
//Entao o no pai (anterior) e o no onde deve ser feita a insercao, pois alcancou um no folha
*flag = 1;
*valorRetorno = valor;
return (NULL);
} else {
//Executa a busca pelo no onde o valor deve ser inserido
pos = buscaBinaria (no, valor);
//Identifica se a chave ja esta presente na arvore
if ( (pos < no->contChaves) &&
(no->chaves[pos] == valor)
){
printf("O valor da chave ja esta presente na arvore B!\n");
*flag = 0;
} else {
//Desce na arvore, buscando pelo no folha onde deve ocorrer a insercao
if ( no->chaves[pos] < valor)
pos++;
filhoDir = insere(no->filhos[pos], valor, flag, valorRetorno); //Executa chamada recursiva
if ( *flag ) { //Se ocorreu a descida como esperado, entao insere o valor no no
if ( no->contChaves < MAX_CHAVES) { //Verifica se ha espaço no no
insereChave(no, *valorRetorno, filhoDir);
*flag = 0;
} else { //Entao e preciso dividir o no p/ poder inserir o valor
noAux = alocaNovoNo();
meio = no->chaves[MIN_CHAVES];
//Insere metade das chaves no novo no
noAux->filhos[0] = no->filhos[MIN_CHAVES+1];
for ( i = MIN_CHAVES + 1;
i < MAX_CHAVES;
i++ ) {
insereChave( noAux, no->chaves[i], no->filhos[i+1] );
}
//Atualiza o no ("apaga" as chaves transferidas
for ( i = MIN_CHAVES;
i < MAX_CHAVES;
i++ ) {
no->chaves[i] = 0;
no->filhos[i+1] = NULL;
no->contChaves--;
}
//no->contChaves = MIN_CHAVES;
//Verifica em qual dos novos nos o valor deve ser inserido e executa
if ( pos <= MIN_CHAVES) {
insereChave(no, *valorRetorno, filhoDir);
} else {
insereChave(noAux, *valorRetorno, filhoDir);
}
//Retorna o elemento do meio para ser inserido no no pai e o filho direito da chave central
*flag = 1;
*valorRetorno = meio;
return (noAux);
}
}
}
}
}
// funcao principal de insercao na caorvore B (funcao a ser chamada pelas funções externas)
tipoArvB *insereArvB (tipoArvB *raiz, long int valor) {
int flag;
long int valorRetorno, i;
tipoArvB *filhoDir, *novaRaiz;
filhoDir = insere (raiz, valor, &flag, &valorRetorno);
//Verifica se ocorreu a descida na arvore adequadamente, se ha a necessidade de um novo no como raiz
if ( flag ) {
novaRaiz = alocaNovoNo();
novaRaiz->contChaves = 1;
novaRaiz->chaves[0] = valorRetorno;
novaRaiz->filhos[0] = raiz;
novaRaiz->filhos[1] = filhoDir;
novaRaiz->folha = 0;
return (novaRaiz);
} else {
return (raiz);
}
}
//funcao para impressao da estrutura arvore B (em pre-ordem)
void imprimeB(tipoArvB *no) {
int i;
if (no != NULL) {
//Imprime as chaves
printf("[");
for ( i = 0; i < no->contChaves; i++ ) {
printf("%ld,", no->chaves[i]);
}
printf("]\n");
//Executa chamada recursiva para os filhos
for ( i = 0; i < no->contChaves + 1; i++ ) {
imprimeB( no->filhos[i] );
}
}
}
int main(int argc, char const *argv[]) {
tipoArvB *arvore;
arvore = NULL;
arvore = insereArvB(arvore, 50);
arvore = insereArvB(arvore, 10);
arvore = insereArvB(arvore, 11);
arvore = insereArvB(arvore, 12);
arvore = insereArvB(arvore, 13);
arvore = insereArvB(arvore, 14);
imprimeB(arvore);
return 0;
}