Problema arvore avl em C

gabriel.c94 · 10 de dezembro de 2014

Pra um trabalho da disciplina de estrutura de dados estou montando uma especie de banco de dados baseado em arvore avl. Primeiramente fazendo como uma arvore binaria normal tudo funciona como deveria, mas quando tento implementar o balanceamento dos nós o programa da crash e não consigo detectar o erro. Segue o codigo completo do programa:

#include <stdio.h>#include <stdlib.h>#include <string.h>//Estruturas para a arvore avl//----------------------------typedef struct node{    struct registry *content;    int fb;    struct node *left;    struct node *right;    struct node *parent;    int height;}node;typedef struct tree{    struct node *root;}tree;typedef struct registry{    int id;    char name[50];    int colums;}registry;//---------------------------//Fim das estruturasvoid initialize_tree(tree *t){    t->root = NULL;}void initialize_node(node *n){    n->content = NULL;    n->fb = 0;    n->left = NULL;    n->right = NULL;    n->parent = NULL;}node *rotate_left(node *n){    node *aux1, *aux2, *aux3, *aux4, *aux5, *aux6, *aux7;    aux1 = n;    aux2 = n->right;    aux3 = n->right->right;    aux4 = n->left;    aux5 = n->right->left;    n->content = aux2->content;    n->left->content = aux1->content;    n->left->left = aux4;    n->left->left->parent = n->left;    n->left->right = aux5;    n->left->right->parent = n->left;    n->right = aux3;    n->right->parent = n;    return n;}node *rotate_right(node *n){    node *aux1, *aux2, *aux3, *aux4, *aux5, *aux6, *aux7;    aux1 = n;    aux2 = n->left;    aux3 = n->left->left;    aux4 = n->right;    aux5 = n->left->right;    n->content = aux2->content;    n->right->content = aux1->content;    n->right->right = aux4;    n->right->right->parent = n->right;    n->right->left = aux5;    n->right->left->parent = n->right;    n->left = aux3;    n->left->parent = n;    return n;}void balance(node *n, registry *r){    if (n->fb > 1 && r->id < n->left->content->id){        n = rotate_right(n);    }    if (n->fb < -1 && r->id > n->right->content->id){        n = rotate_left(n);    }    if (n->fb > 1 && r->id > n->left->content->id){        n->left = rotate_left(n->left);        n = rotate_right(n);    }    if (n->fb < -1 && r->id < n->right->content->id){        n->right = rotate_right(n->right);        n = rotate_left(n);    }}void insert_node(node *t, registry *n, node *p){    if (t->content == NULL){        t->content = n;        node *new_left = malloc(sizeof(node));        node *new_right = malloc(sizeof(node));        initialize_node(new_left);        initialize_node(new_right);        t->left = new_left;        t->right = new_right;        t->parent = p;    }    else if (n->id < t->content->id){        insert_node(t->left, n, t);    }    else if (n->id > t->content->id){        insert_node(t->right, n, t);    }    else if (n->id == t->content->id){        printf("O banco ja contem esse registro\n");    }    t->fb = calc_fb(t);    balance(t, n);}void remove_registry(node *t, int d){    node *aux1;    node *aux2;    node *blank_node1 = malloc(sizeof(node));    initialize_node(blank_node1);    if (t->content == NULL){        printf("Registro nao encontrado!\n");    }    else{        if (t->content->id == d){            if (t->left->content == NULL){                if (t->right->content == NULL){                    if (t->parent->left == t){                        t->parent->left = blank_node1;                    }                    else{                        t->parent->right = blank_node1;                    }                    free(t);                }                else{                    t->content = t->right->content;                    free(t->right);                    t->right = blank_node1;                }            }            else{                if (t->right->content == NULL){                    t->content = t->left->content;                    free(t->left);                    t->left = blank_node1;                }                else{                    aux1 = t->left;                    while (aux1->right->content != NULL){                        aux1 = aux1->right;                    }                    t->content = aux1->content;                    aux1->content = aux1->left->content;                    free(aux1->left);                    aux1->left = blank_node1;                }            }        }        else{            if (t->content->id > d){                remove_registry(t->left, d);            }            else{                remove_registry(t->right, d);            }        }    }}void show_tree(node *n){    if (n->content == NULL){        return;    }    show_tree(n->left);    printf("%d - %s\n", n->content->id, n->content->name);    show_tree(n->right);}void find_and_print_registry(node *n, int d){    if (n->content->id == d){        printf("%d - %s\n", d, n->content->name);    }    else{        if (n->content->id < d){            find_and_print_registry(n->right, d);        }        if (n->content->id > d){            find_and_print_registry(n->left, d);        }    }}struct registry *make_registry(){    struct registry *new_reg = malloc(sizeof(registry));    printf("Qual o id do registro que voce deseja inserir?\n");    scanf("%d", &new_reg->id);    printf("Qual o nome do registro que voce deseja inserir?\n");    scanf("%s", &new_reg->name);    return new_reg;}int height(node *n){    int h1;    int h2;    if ( n->content == NULL ){        return 0;    }    h1 = height(n->left);    h2 = height(n->right);    if (h1 > h2){        return h1 + 1;    }    else{        return h2 + 1;    }}int calc_fb(node *n){    return (height(n->left) - height(n->right));}void menu(node *main_node){    int option = -1;    int option2;    registry *new_entry;    while (option != 0){        printf("\nDigite:\n0 - Para sair\n1 - Para inserir novo registro\n2 - Para remover um registro\n3 - Para buscar e imprimir um registro\n4 - Para ver todos os registros\n\n");        scanf("%d", &option);        switch (option){            case 1: new_entry = make_registry();                    insert_node(main_node, new_entry, NULL);                    break;            case 2: printf("Qual o id do registro que voce deseja remover?\n");                    scanf("%d", &option2);                    remove_registry(main_node, option2);                    break;            case 3: printf("Qual o id do registro que voce deseja buscar?\n");                    scanf("%d", &option2);                    find_and_print_registry(main_node, option2);                    break;            case 4: show_tree(main_node);                    printf("Altura da arvore: %d\n", height(main_node));        }    }}void main(){    struct tree *new_tree = malloc(sizeof(tree));    initialize_tree(new_tree);    struct node *main_node = malloc(sizeof(node));    initialize_node(main_node);    menu(main_node);}

Se alguem puder dar ajuda ia ser otimo, to a dois dias parado no mesmo problema :/

dontpanic · 10 de dezembro de 2014

Eu passei o código aqui pelo debugger, a tua função de rodar a esquerda e rodar a direita tá fazendo com que as folhas de um nó apontem pra ele mesmo em alguns casos, daí quando você vai inserir um outro membro a tua função 'insert_node' fica em loop infinito e o programa trava.

Você tá fazendo as rotações com as folhas, mas o certo é girar o pai das folhas.

Uma coisa que eu notei é que você tá tratando apenas dois tipos de rotação... mas na verdade existem 4:

- Inserir (1)Peso de [1]: 0 (balanceado)Peso de [2]: -1 (balanceado)Peso de [3]: -2 (gira pra direita           [3]           [2]        [2]      ---> [1]   [3]     [1]    - Inserir (3)Peso de [3]: 0Peso de [2]: +1Peso de [1]: +2 (gira pra esquerda     [1]                 [2]        [2]      ---> [1]   [3]           [3]- Inserir (2)Peso de [2]: 0Peso de [3]: -1Peso de [1]: +2 (gira uma vez pra esquerda, outra pra direita)     [1]             [1]                 [2]        [3]     --->    [2]     --->  [1]   [3]     [2]                   [3]    (o quarto tipo é a mesma coisa, só que pros lados contrários)

Abranger os 4 tipos apenas com duas funções vai deixar você maluco. Amanhã você tá rasgando dinheiro.

Eu acredito que quanto mais modular um programa seja, melhor pro programador e pra quem vai ver o código depois, mas nesse caso você pode facilitar tua vida já balanceando a árvore no momento da inserção. Em vez de usar esse esquema de testar as alturas que você criou, você pode simplesmente fazer uso do peso dos pais de cada folha inserida e testar que tipo de inserção fazer.

Recomendo também no final fazer a limpeza dos teus mallocs.

void fazerLimpezaGeralDaCasa() {    // percorre a árvore, desacolando os registros e depois os nós}int main() {...menu();fazerLimpezaGeral();return 0;}

gabriel.c94 · 13 de dezembro de 2014

Obrigado pela resposta, tentei refazer as funções de rotação, dessa vez fiz 1 para cada caso, mas mesmo assim algo ainda esta dando errado :/
Do jeito que fiz as funções de inserir, eu sempre tenho o nó da esquerda e da direita de cada ultima no de cada subarvore como um nó sem conteudo, desse jeito, quando vou inserir precisa apenas adicionar o conteudo ao nó ja criado e criar dois outros nó vazios abaixo dele. Mas não sei se isso esta atrapalhando o balanceamento. Fiz funçoes que tiram essa nós vazios antes de balancear e acrescentam eles de volta depois, mas ainda não funciona.

O codigo esta desse jeito agora:

#include <stdio.h>#include <stdlib.h>#include <string.h>//Estruturas para a arvore avl//----------------------------typedef struct node{    struct registry *content;    int fb;    struct node *left;    struct node *right;    struct node *parent;    int height;}node;typedef struct tree{    struct node *root;}tree;typedef struct registry{    int id;    char name[50];    int colums;}registry;//---------------------------//Fim das estruturasvoid initialize_tree(tree *t){    t->root = NULL;}void initialize_node(node *n){    n->content = NULL;    n->fb = 0;    n->left = NULL;    n->right = NULL;    n->parent = NULL;}void clean_blanks(node *n){    free(n->left);    free(n->right);    n->left = NULL;    n->right = NULL;}void add_blanks(node *n){    node *new_left = malloc(sizeof(node));    node *new_right = malloc(sizeof(node));    initialize_node(new_left);    initialize_node(new_right);    n->left = new_left;    n->right = new_right;}void rotate_left_twice(node *n){    node *k1,*k2,*k3=n,*b,*c;    k1=k3->left;    k2=k1->right;    b=k2->left;    c=k2->right;    //Clean blanks    clean_blanks(k1->left);    clean_blanks(k2->left);    clean_blanks(k2->right);    clean_blanks(k3->right);    k1->right=b;    k3->left=c;    k2->left=k1;    k2->right=k3;    n=k2;    //Add blanks back    add_blanks(n->left->left);    add_blanks(n->left->right);    add_blanks(n->right->left);    add_blanks(n->right->right);}void rotate_left(node *n){    struct node *k1,*k2=n,*x,*y,*z;    k1=k2->left;    x=k1->left;    y=k1->right;    z=k2->right;    //Clean blanks    clean_blanks(x);    clean_blanks(y);    clean_blanks(z);    k1->right=k2;    k2->left=y;    n=k1;    //Add blanks back    add_blanks(x);    add_blanks(y);    add_blanks(z);}void rotate_right_twice(node *n){    struct node *k1=n,*k2,*k3,*b,*c;    k3=k1->right;    k2=k3->left;    b=k2->left;    c=k2->right;    //Clean blanks    clean_blanks(k1->left);    clean_blanks(k2->left);    clean_blanks(k2->right);    clean_blanks(k3->right);    k1->right=b;    k3->left=c;    k2->left=k1;    k2->right=k3;    n=k2;    //Add blanks back    add_blanks(n->left->left);    add_blanks(n->left->right);    add_blanks(n->right->left);    add_blanks(n->right->right);}void rotate_right(node *n){    struct node *k1=n,*k2,*x,*y,*z;    k2=k1->right;    x=k1->left;    y=k2->left;    z=k2->right;    //Clean blanks    clean_blanks(x);    clean_blanks(y);    clean_blanks(z);    k1->right=y;    k2->left=k1;    n=k2;    //Add blanks back    add_blanks(x);    add_blanks(y);    add_blanks(z);}void balance(node *n, registry *r){    if (n->fb > 1 && r->id < n->left->content->id){        rotate_right(n);    }    if (n->fb < -1 && r->id > n->right->content->id){        rotate_left(n);    }    if (n->fb > 1 && r->id > n->left->content->id){        rotate_right_twice(n);    }    if (n->fb < -1 && r->id < n->right->content->id){        rotate_left_twice(n);    }}void insert_node(node *t, registry *n, node *p){    if (t->content == NULL){        t->content = n;        node *new_left = malloc(sizeof(node));        node *new_right = malloc(sizeof(node));        initialize_node(new_left);        initialize_node(new_right);        t->left = new_left;        t->right = new_right;        t->parent = p;    }    else if (n->id < t->content->id){        insert_node(t->left, n, t);    }    else if (n->id > t->content->id){        insert_node(t->right, n, t);    }    else if (n->id == t->content->id){        printf("O banco ja contem esse registro\n");    }    t->fb = calc_fb(t);    balance(t, n);}void remove_registry(node *t, int d){    node *aux1;    node *aux2;    node *blank_node1 = malloc(sizeof(node));    initialize_node(blank_node1);    if (t->content == NULL){        printf("Registro nao encontrado!\n");    }    else{        if (t->content->id == d){            if (t->left->content == NULL){                if (t->right->content == NULL){                    if (t->parent->left == t){                        t->parent->left = blank_node1;                    }                    else{                        t->parent->right = blank_node1;                    }                    free(t);                }                else{                    t->content = t->right->content;                    free(t->right);                    t->right = blank_node1;                }            }            else{                if (t->right->content == NULL){                    t->content = t->left->content;                    free(t->left);                    t->left = blank_node1;                }                else{                    aux1 = t->left;                    while (aux1->right->content != NULL){                        aux1 = aux1->right;                    }                    t->content = aux1->content;                    aux1->content = aux1->left->content;                    free(aux1->left);                    aux1->left = blank_node1;                }            }        }        else{            if (t->content->id > d){                remove_registry(t->left, d);            }            else{                remove_registry(t->right, d);            }        }    }}void show_tree(node *n){    if (n->content == NULL){        return;    }    show_tree(n->left);    printf("%d - %s\n", n->content->id, n->content->name);    show_tree(n->right);}void find_and_print_registry(node *n, int d){    if (n->content->id == d){        printf("%d - %s\n", d, n->content->name);    }    else{        if (n->content->id < d){            find_and_print_registry(n->right, d);        }        if (n->content->id > d){            find_and_print_registry(n->left, d);        }    }}struct registry *make_registry(){    struct registry *new_reg = malloc(sizeof(registry));    printf("Qual o id do registro que voce deseja inserir?\n");    scanf("%d", &new_reg->id);    printf("Qual o nome do registro que voce deseja inserir?\n");    scanf("%s", &new_reg->name);    return new_reg;}int height(node *n){    int h1;    int h2;    if ( n->content == NULL ){        return 0;    }    h1 = height(n->left);    h2 = height(n->right);    if (h1 > h2){        return h1 + 1;    }    else{        return h2 + 1;    }}int calc_fb(node *n){    return (height(n->left) - height(n->right));}void menu(node *main_node){    int option = -1;    int option2;    registry *new_entry;    while (option != 0){        printf("\nDigite:\n0 - Para sair\n1 - Para inserir novo registro\n2 - Para remover um registro\n3 - Para buscar e imprimir um registro\n4 - Para ver todos os registros\n\n");        scanf("%d", &option);        switch (option){            case 1: new_entry = make_registry();                    insert_node(main_node, new_entry, NULL);                    break;            case 2: printf("Qual o id do registro que voce deseja remover?\n");                    scanf("%d", &option2);                    remove_registry(main_node, option2);                    break;            case 3: printf("Qual o id do registro que voce deseja buscar?\n");                    scanf("%d", &option2);                    find_and_print_registry(main_node, option2);                    break;            case 4: show_tree(main_node);                    printf("Altura da arvore: %d\n", height(main_node));        }    }}void main(){    struct tree *new_tree = malloc(sizeof(tree));    initialize_tree(new_tree);    struct node *main_node = malloc(sizeof(node));    initialize_node(main_node);    menu(main_node);}

Preciso entregar esse trabalho domingo, alguem da uma luz pfv

dontpanic · 13 de dezembro de 2014

Na hora de rotacionar as folhas, você precisa levar em conta os parents.

Vou tentar explicar:

[raiz] = [5]            [6]               [7]

No caso acima, você precisa girar o [5] pra esquerda, certo?

Então:

[5]->right = [6]->left

[6]->left = [5]

Isso deixaria o [5], [6] e [7] balanceados, mas a arvore ficaria com a raiz errada, e o [5] ficou sem parent.

            [6][raiz] = [5]   [7]

Por isso que precisa levar em consideração os parents:

rotate_right(n) {    aux = n->right; // guarda [6]    if (n->parent < n) // n está a direita do parent        n->parent->right = n->right; // o parent de [5] agora aponta pra [6] pela direita    if (n->parent > n) // n está a esquerda do parent        n->parent->left = n->right; // o parent de [5] agora aponta pra [6] pela esquerda    n->right->parent = n->parent; // o parent de [6] agora é o parente de [5]    n->parent = aux; // e o parent de [5] é [6]        n->right = n->right->left; // direita de [5] aponta agora pra esquerda de [6]    aux->left = n; // esquerda de [6] aponta agora pra [5]}

Além disso achei um erro pequeno na parte de criar registro:

struct registry *make_registry(){    ...    scanf("%s", &new_reg->name); // <---------- não precisa do & alí    return new_reg;}

E você precisa também de algum jeito de guardar a raiz no teu código. Senão não vai conseguir fazer as rotações.

    struct tree *new_tree = malloc(sizeof(tree));    initialize_tree(new_tree); // inicializou a raiz    struct node *main_node = malloc(sizeof(node));    initialize_node(main_node);    menu(main_node); // mas no menu você tá passando apenas uma folha que vai provavelmente mudar de posição na árvore ao longo do código                     // então o programa não tem como associar a raiz com nenhuma folha

Pra lidar com os vários tipos de rotação, com a RAIZ, etc, o teu código precisaria sofrer várias pequenas alterações.

Como você disse que o projeto é pra amanhã, apesar do teu código estar bem legal, eu te recomendaria pegar algo pronto do google, dá uma estudada nele e adapta pra tua struct.