Ir ao conteúdo
  • Cadastre-se

C Problema no Código btree


lala25

Posts recomendados

estou com problemas em um código que deleta um elemento de uma Btree



//tad

enum KeyStatus {Duplicate,SearchFailure,Success,InsertIt,LessKeys};



typedef struct tnode
{
    int size;
    int keys[M-1];
    struct tnode *p[M];
}BTREE;



void deleteBTREE(BTREE *root,int key){
    BTREE *bst;
    enum KeyStatus value;
    value = del(root,key);

    switch (value)
    {
    case SearchFailure:
        printf("Key %d is not available\n",key);
        break;
    case LessKeys:
        bst = root;
        root = root->p[0];
        free(bst);
        break;
    }
}

enum KeyStatus del(BTREE *ptr, int key)
{
    int pos, i, pivot, n ,min;
    int *key_arr;
    enum KeyStatus value;
    BTREE **p,*lptr,*rptr;

    if (ptr == NULL){
        printf("\n B-TREE nao existe\n");
        return SearchFailure;
    }

    n=ptr->size;
    key_arr = ptr->keys;
    p = ptr->p;
    min = (M - 1)/2;/*Numero minimo de chaves*/

    //Pesquisar a chave para deletar
    pos = searchKeyInNodeBTREE(key, key_arr, n);
    if (p[0] == NULL)
    {
        if (pos == n || key < key_arr[pos])
            return SearchFailure;

        for (i=pos+1; i < n; i++)
        {
            key_arr[i-1] = key_arr;
            p = p[i+1];
        }
        return --ptr->size >= (ptr==root ? 1 : min) ? Success : LessKeys;
    }

    if (pos < n && key == key_arr[pos])
    {
        BTREE *qp = p[pos], *qp1;
        int nkey;
        while(1)
        {
            nkey = qp->size;
            qp1 = qp->p[nkey];
            if (qp1 == NULL)
                break;
            qp = qp1;
        }
        key_arr[pos] = qp->keys[nkey-1];
        qp->keys[nkey - 1] = key;
    }

    value = del(p[pos], key);
    if (value != LessKeys)
        return value;

    if (pos > 0 && p[pos-1]->n > min)
    {
        pivot = pos - 1;
        lptr = p[pivot];
        rptr = p[pos];
        rptr->p[rptr->size + 1] = rptr->p[rptr->size];
        for (i=rptr->size; i>0; i--)
        {
            rptr->keys = rptr->keys[i-1];
            rptr->p = rptr->p[i-1];
        }
        rptr->size++;
        rptr->keys[0] = key_arr[pivot];
        rptr->p[0] = lptr->p[lptr->size];
        key_arr[pivot] = lptr->keys[--lptr->size];
        return Success;
    }

    if (pos < n && p[pos + 1]->size > min)
    {
        pivot = pos;
        lptr = p[pivot];
        rptr = p[pivot+1];

        lptr->keys[lptr->size] = key_arr[pivot];
        lptr->p[lptr->size + 1] = rptr->p[0];
        key_arr[pivot] = rptr->keys[0];
        lptr->size++;
        rptr->size--;
        for (i=0; i < rptr->size; i++)
        {
            rptr->keys = rptr->keys[i+1];
            rptr->p = rptr->p[i+1];
        }
        rptr->p[rptr->size] = rptr->p[rptr->size + 1];
        return Success;
    }

    if(pos == n)
        pivot = pos-1;
    else
        pivot = pos;

    lptr = p[pivot];
    rptr = p[pivot+1];

    lptr->keys[lptr->size] = key_arr[pivot];
    lptr->p[lptr->size + 1] = rptr->p[0];
    for (i=0; i < rptr->size; i++)
    {
        lptr->keys[lptr->size + 1 + i] = rptr->keys;
        lptr->p[lptr->size + 2 + i] = rptr->p[i+1];
    }
    lptr->size = lptr->size + rptr->size +1;
    free(rptr);
    for (i=pos+1; i < n; i++)
    {
        key_arr[i-1] = key_arr;
        p = p[i+1];
    }
    return --ptr->size >= (ptr == root ? 1 : min) ? Success : LessKeys;
}
 

 

Link para o comentário
Compartilhar em outros sites

  • 2 semanas depois...

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...