7

Tenho que implementar uma avl que recebe 10 mil números aleatórios de 1 a 1000 000, logo após isso, tenho que remover 1 mil números aleatórios, ambos retirados de arquivos .txt, eu consigo inserir normalmente, mas na hora de remover, ate consigo remover alguns, porem o cmd para de funcionar, gostaria da ajuda e vocês.

Abaixo o código para gerar os números

[Atualização] rastreei e vi que o problema esta quando tenho que remover um número duplicado com 2 filhos. por exemplo. na arvore tem 2 numeros 500, e na função para remover pede para remover o 500, para remover um no com dois filhos tenho que pegar o menor no da arvore, pois é ai que acontece o loop infinito.

 #include 
 #include 
 #include 

typedef struct no_arvore { int n; struct no_arvore *esq; struct no_arvore *dir; } no_arvore;

//declaração devariaveis globais para contar as rotações duplas, simples e nos visitados na inserção int Rdupla = 0; int rSimples = 0; int nVisitados = 0; //fim da declaração.

int comparacoes = 0;

no_arvore *remover_no_arvore(no_arvore *r, int x); int fator_balanceamento(no_arvore *r); no_arvore *rotacao_simples_direita(no_arvore *r); no_arvore *rotacao_simples_esquerda(no_arvore *r);

//Função que verifica se um nó está balanceado e faz as rotações necessárias. no_arvore *verifica_balanceamento(no_arvore *r) { int fb; fb = fator_balanceamento(r); //Após inserir o nó para esq ou dir, verificar Fator de bal. if (fb < -1) { if (fator_balanceamento(r->esq) > 0) { //Rotação dupla a direita. Rdupla++; //conta rotações duplas. r->esq = rotacao_simples_esquerda(r->esq); } r = rotacao_simples_direita(r); //Rotação simples a esquerda. rSimples++; //conta rotações simples. } else if (fb > 1) { if (fator_balanceamento(r->dir) < 0) { //Rotação dupla a esquerda. Rdupla++; //conta rotações duplas. r->dir = rotacao_simples_direita(r->dir); } r = rotacao_simples_esquerda(r); //Rotação simples a direita. rSimples ++; //conta rotações simples. } return r; }

no_arvore *insere_arvore(no_arvore *r, int num) { if (r == NULL) { //Se a árvore estiver vazia, inserir o nó. r = (no_arvore *)malloc(sizeof(no_arvore)); //Alocar o nó. r->n = num; //Atribuir um valor para o nó. r->dir = NULL; //Iniciar o filho direito. r->esq = NULL; //Iniciar o filho esquerdo. } else { nVisitados ++; //soma o nos visitados. //Se a árvore não estiver vazia, verificar se num é menor que n. if (num < r->n) { //Se for menor, inserir a esquerda. r->esq = insere_arvore(r->esq, num); } else { //Senão, inserir a direita. r->dir = insere_arvore(r->dir, num); } r = verifica_balanceamento(r); //Verificar balanceamento da árvore. } return r; }

void busca_in_order(no_arvore *r, int num) { //Verificar se a árvore não está vazia. if (r != NULL) { if(r -> n != num){ comparacoes++; //Se a árvore não estiver vazia, executar a busca. busca_in_order(r->esq, num); //1 - Buscar na árvore esquerda. //printf("%d ",r->n); //2 - Mostrar a raiz. busca_in_order(r->dir, num); //3 - Buscar na árvore direita.

    }else{
        //printf("%d ", r -> n);

        }
}
//Se a árvore estiver vazia, não executar a busca.

}

void busca_pre_order(no_arvore *r) { //Verificar se a árvore não está vazia. if (r != NULL) { //Se a árvore não estiver vazia, executar a busca. printf("%d ",r->n); //1 - Mostrar a raiz. busca_pre_order(r->esq); //2 - Buscar na árvore esquerda. busca_pre_order(r->dir); //3 - Buscar na árvore direita. } //Se a árvore estiver vazia, não executar a busca. }

void busca_pos_order(no_arvore *r) { //Verificar se a árvore não está vazia. if (r != NULL) { //Se a árvore não estiver vazia, executar a busca. busca_pos_order(r->esq); //1 - Buscar na árvore esquerda. busca_pos_order(r->dir); //2 - Buscar na árvore direita. printf("%d ",r->n); //3 - Mostrar a raiz. } //Se a árvore estiver vazia, não executar a busca. }

int altura_arvore(no_arvore *r) { if (r== NULL) { return -1; } else { int altEsq, altDir; altEsq = altura_arvore(r->esq); altDir = altura_arvore(r->dir); if (altEsq > altDir) { return altEsq + 1; } else { return altDir + 1; } } }

int fator_balanceamento(no_arvore *r) { //Fator de Balanceamento = Altura da sub-arvore direita - Altura da sub-arvore esquerda. return altura_arvore(r->dir) - altura_arvore(r->esq); }

no_arvore *rotacao_simples_direita(no_arvore *r) { no_arvore *q = r->esq; r->esq = q->dir; q->dir = r; return q; }

no_arvore *rotacao_simples_esquerda(no_arvore *r) { no_arvore *q = r->dir; r->dir = q->esq; q->esq = r; return q; }

//Funçães que retorna o endereço do menor nó da árvore. no_arvore *menor_no_arvore(no_arvore *r) { no_arvore *aux = r; while (aux->esq != NULL) { //Procurar o nó mais a esquerda (menor nó da árvore). //printf("aux: %d\n", aux->n); aux = aux->esq; } //printf("aux: %d\n", aux->n); return aux; //Retornar o endereço do menor nó da árvore. }

//Função que remove um nó que é folha (não possui filhos). no_arvore *remover_folha(no_arvore *r) { printf("\nA folha %d foi removida com sucesso!\n", r->n); //getch(); free(r); return NULL; }

no_arvore *remover_1filho_esquerda(no_arvore *r) { no_arvore *aux = r->esq; printf("\n numero %d foi removido com sucesso!\n", r->n); free(r); return aux; }

no_arvore *remover_1filho_direita(no_arvore *r) { no_arvore *aux = r->dir; printf("\n numero %d foi removido com sucesso!\n", r->n); free(r); return aux; }

no_arvore *remover_2filhos(no_arvore *r) { no_arvore *aux; int x; aux = menor_no_arvore(r->dir); //auxiliar recebe o endereço do menor nó da árvore. //printf("aux: %d\n", aux->n); x = aux->n; //guardar o valor do auxiliar em uma variável x. r = remover_no_arvore(r,x); //remover da árvore o nó que substituirá o nó com 2 filhos.

r->n = x;                       //substituir o valor do nó com 2 filhos.
return r;

}

//Função para verificar o tipo de nó que será removido. no_arvore *remover_no(no_arvore *r) { //Verificar se o nó é uma folha (Não possui filhos). if (r->dir == NULL && r->esq == NULL) { //printf("O no %d eh uma folha.\n", r->n); r = remover_folha(r); } else { if (r->dir == NULL) { //printf("O no %d possui 1 filho para esquerda.\n", r->n); r = remover_1filho_esquerda(r); } else { if (r->esq == NULL) { //printf("O no %d possui 1 filho para direita.\n", r->n); r = remover_1filho_direita(r); } else { //printf("O no %d possui 2 filhos.\n", r->n); r = remover_2filhos(r); } } } return r; }

no_arvore *remover_no_arvore(no_arvore *r, int x) { //Verificar se a árvore não está vazia. if (r != NULL) { //Se a árvore não está vazia, buscar o elemento x. if (r->n == x) { //1 - Verificar se o elemento x está na raiz. //printf("ENCONTREI!: %d\n", r->n); r = remover_no(r); //Chamar a função para remover o nó. } else { //Se x não está na raiz, verificar para qual lado x está. if (x < r->n) { //Fazer chamada recursiva para a esquerda. r->esq = remover_no_arvore(r->esq, x); } else { //Fazer chamada recursiva para a direita. r->dir = remover_no_arvore(r->dir, x); } r = verifica_balanceamento(r); //Verificar balanceamento da árvore. } } else { printf("Elemento nao encontrado: %d\n", x); } return r; }

no_arvore *inserir_aleatorio(no_arvore *r){ int num;

char url[]="aleatorios.txt";
FILE *Ale;
Ale = fopen(url, "r");
if(Ale == NULL){
    printf("Error ");
}else{
    while(fscanf(Ale, "%d\n", &num)!=EOF){
        r = insere_arvore(r, num);
    }
}
fclose(Ale);

return r;

}

void busca_aleatorio_1000(no_arvore *r){ int num;

char url[]="aleatorios1000.txt";
FILE *Ale;
Ale = fopen(url, "r");
if(Ale == NULL){
    printf("Error ");
}else{
    while(fscanf(Ale, "%d\n", &num)!=EOF){

        busca_in_order(r, num);
    }
}
fclose(Ale);

}

no_arvore *remover_no_arvore_aleatorio(no_arvore *r) {

int num;

char url[]="aleatorios1000Remocao.txt";
FILE *Ale;
Ale = fopen(url, "r");
if(Ale == NULL){
    printf("Error ");
}else{
    while(fscanf(Ale, "%d\n", &num)!=EOF){

        r = remover_no_arvore(r, num);

    }
}
fclose(Ale);
    return r;

}

int main() {

no_arvore *raiz = NULL;

raiz = inserir_aleatorio(raiz);
printf("\nrotacoes simples: %d",rSimples - Rdupla);
printf("\nrotacoes duplas: %d", Rdupla);
printf("\nvisitas: %d\n\n",nVisitados);

remover_no_arvore_aleatorio(raiz);

system("pause");

} inserção

     # include < stdio.h>
     # include < stdlib.h>
     # include < time.h>

int main(){ int i; FILE *fp; fp = fopen("aleatorios.txt", "w"); if(fp == NULL){ printf("erro.\n"); return 1; } srand( (unsigned)time(NULL) ); for(i=1; i<10000; i++){ fprintf(fp, "%d\n", 1 + rand()% 1000000); } fclose(fp); return 0;

}

#include < stdio.h> #include < stdlib.h> #include < time.h> int main(){ int i; FILE *fp; fp = fopen("aleatorios1000Remocao.txt", "w"); if(fp == NULL){ printf("erro.\n"); return 1; } srand( (unsigned)time(NULL) ); for(i=1; i<1000; i++){ fprintf(fp, "%d\n", 1 + rand()% 1000000); } fclose(fp); return 0; } <code>
1
  • Na função de remover "filho" você dá free e depois atribui NULL? Acredito que seja necessário uma atribuição, já que só é possível saber se está no fim da árvore quando os dois filhos são NULL. Commented 19/06/2016 às 5:50

1 Resposta 1

7

Seu problema está na remoção com dois filhos.

no_arvore *remover_2filhos(no_arvore *r) {
    no_arvore *aux;
    int x;
    aux = menor_no_arvore(r->dir);  //auxiliar recebe o endereço do menor nó da árvore.
    //printf("aux: %d\n", aux->n);
    x = aux->n;                     //guardar o valor do auxiliar em uma variável x.
    r = remover_no_arvore(r,x);     //remover da árvore o nó que substituirá o nó com 2 filhos.

r->n = x;                       //substituir o valor do nó com 2 filhos.
return r;


}

Veja o que o seu código está fazendo:

Estado inicial da função

Elemento encontrado em menor_no_arvore(r->dir)

valor recebido por x

Repare que tudo aconteceu como deveria, entretado nesta linha você está chamando a função de remoção novamente:

r = remover_no_arvore(r,x); 

Agora, a mesma árvore da primeira imagem é recebida, ele verifica que a raíz contém o elemento desejado para remoção, identifica que possui dois filhos, busca o menor no filho da direita, encontra 500, chama a função de remoção para o número 500, identifica que é o elemento da raiz, identifica que possui dois filhos, busca o menor filho da direita, encontra 500, chama a função de remoção para o número 500, identifica que é o elemento da raiz, identifica que possui dois filhos, busca o menor filho da direita, encontra 500, chama remoção para o número 500... ... ... ... ...

O problema é que você está identificando corretamente a existência de dois filhos, entretanto você deseja remover o menor filho da direita e a função destacada acima passa o valor do menor filho da direita a ser removido e a mesma raíz ou subárvore é passada para esta função.

Ao invés de:

r = remover_no_arvore(r,x); 

Tente:

r = remover_no_arvore(r->dir,x); 

Assim você garante que você deseja remover o elemento x que se encontra na direita da árvore, ao invés de passar a própria árvore para remover o elemento x.

O problema que você está tendo é uma recursão infinita, como cada chamada de função cria uma pilha para que o programa saiba voltar de onde ele veio, a criação de pilhas sem fim gerará o problema que, em inglês, chama-se StackOverflow (estouro de pilha).

Se isso estiver correto, você veio ao site StackOverflow buscar uma solução para StackOverflow :D

Tente corrigir isto e veja se funcionou.

1
  • 2
    Obrigado Murillo, eu não tinha percebido isso(talvez tinha sido o sono), esta funcionando perfeitamente agora, adicionei outras linha de código, porque as vezes a função remover_no_arvore, retornava nullo e dava problema em atribuir o x. enfim, funcionando perfeitamente, Commented 19/06/2016 às 19:10

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .