Tree b is partitioning the wrong node

Asked

Viewed 35 times

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;
    }

1 answer

0

Your binary search function is incorrect. if (start == end) is never satisfied because of the while condition. I changed other conditions so that it always returns the position where the value should be inserted. Follow my version:

    //Funcao que executa a busca binaria no no
    int buscaBinaria(tipoArvB *raiz, long int valor) {
    int inicio, meio = 0, fim;

    inicio = 0;
    fim = raiz->contChaves - 1;

    while (inicio <= fim) {
        if (inicio == fim && raiz->chaves[inicio] >= valor) {
            return inicio;
        }
        else if (inicio == fim && raiz->chaves[inicio] <= valor) {
            return fim + 1;
        }
        else {
            meio = (inicio + (fim - inicio) / 2);
        }

        if (raiz->chaves[meio] >= valor && raiz->chaves[meio-1] <= valor) {
            return meio;
        }
        else {
            if (valor < raiz->chaves[meio])
                fim = (meio - 1);
            else
                inicio = (meio + 1);
        }
    }
    return (meio);
}

Browser other questions tagged

You are not signed in. Login or sign up in order to post.