Removal of random numbers in AVL tree

Question

I have to implement an avl that gets 10,000 random numbers from 1 to 1000,000, right after that, I have to remove 1,000 random numbers, both taken from files. txt, I can enter normally, but when it comes to removing, I can even remove some, but cmd stops working, I’d like the help and you guys.

Below the code to generate the numbers

[Updating] I tracked down and saw that the problem is when I have to remove a duplicate number with 2 children. for example. in the tree has 2 numbers 500, and in the function to remove asks to remove the 500, to remove a no with two children I have to catch the smallest one in the tree, because that’s where happens the infinite loop.

 #include 
 #include 
 #include 

typedef struct no_tree { int n. struct no_tree *Esq; struct no_tree *dir; } no_tree;

//global devariable declaration to count the double, single and visited rotations in the insert int Rdupla = 0; int rSimples = 0; int nVisitados = 0; //end of declaration.

int comparisons = 0;

no_tree *remover_no_tree(no_tree *r, int x); int factor_balancing (tree no_r); no_tree *rotacao_simples_right (no_tree *r); no_tree *rotacao_simples_left(no_tree *r);

//Function that checks if a node is balanced and makes the necessary rotations. no_tree *check_balancing(no_tree *r) { int fb; fb = balancing factor(r); //After inserting the node for Esq or dir, check bal factor. if (fb < -1) { if (factor_balancing(r->Esq) > 0) ? //Double right rotation. Rdupla++; //count double rotations. r->Esq = rotacao_simples_left(r->Esq); } r = rotacao_simples_right(r); //Single left rotation. rSimples++; //account single rotations. } Else if (fb > 1) { if (factor_balancing(r->dir) < 0) ? //Double left rotation. Rdupla++; //count double rotations. r->dir = rotacao_simples_right(r->dir); } r = rotacao_simples_left(r); //Single right rotation. rSimples ++; //account single rotations. } Return; }

no_tree *inse_tree(no_tree *r, int num) { if (r == NULL) ? //If the tree is empty, insert the node. r = (no_tree *)malloc(sizeof(no_tree)); //Allocate node. r->n = num; //Assign a value to the node. r->dir = NULL; //Start the right child. r->Esq = NULL; //Start left child. } Else { nVisitados ++; //sum o in the visited ones. //If the tree is not empty, check if one is less than n. if (num < r->n) ' //If smaller, insert left. r->Esq = insert tree(r->Esq, num); } Else ː //Otherwise insert right. r->dir = insert tree(r->dir, num); } r = balancing(r); //Check tree balance. } Return; }

void busca_in_order(no_tree *r, int num) { //Check that the tree is not empty. if (r != NULL) { if(r -> n != num){ comparisons++; //If the tree is not empty, execute the search. busca_in_order(r->Esq, num); //1 - Search in left tree. //printf("%d ",r->n); //2 - Show root. busca_in_order(r->dir, num); //3 - Search in right tree.

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

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

}

void busca_pre_order(no_tree *r) { //Check that the tree is not empty. if (r != NULL) { //If the tree is not empty, execute the search. printf("%d ",r->n); //1 - Show root. busca_pre_order(r->Esq); //2 - Search in left tree. busca_pre_order(r->dir); //3 - Search in the right tree. } //If the tree is empty, do not perform the search. }

void busca_pos_order(tree no_tree *r) { //Check that the tree is not empty. if (r != NULL) { //If the tree is not empty, execute the search. busca_pos_order(r->Esq); //1 - Search in left tree. busca_pos_order(r->dir); //2 - Search in the right tree. printf("%d ",r->n); //3 - Show root. } //If the tree is empty, do not perform the search. }

int tree (tree number *r) { if (r== NULL) { Return -1; } Else { int altEsq, altDir; altEsq = tree (r->Esq); altDir = tree (r->dir); if (altEsq > altDir) { Return altEsq + 1; } Else { Return altDir + 1; } } }

int factor_balancing(tree no_r) { //Balancing Factor = Height of right sub-tree - Height of left sub-tree. Tree (r->dir) - tree (r->Esq); }

no_tree *rotacao_simples_right (no_tree *r) { no_tree *q = r->Esq; r->Esq = q->dir; q->dir = r; Return q; }

no_tree *rotacao_simples_left(no_tree *r) { no tree *q = r->dir; r->dir = q->Esq; q->Esq = r; Return q; }

//Functions that returns the address of the smallest node in the tree. no_tree *menor_no_tree(no_tree *r) { no_tree *aux = r; while (aux->Esq != NULL) ? //Find the leftmost node (smallest tree node). //printf("aux: %d n", aux->n); aux = aux->Esq; } //printf("aux: %d n", aux->n); Return aux; //Return the address of the smallest tree node. }

//Function that removes a node that is sheet (has no children). no_tree *remover_sheet(no_tree *r) { printf(" on sheet %d has been successfully removed! n", r->n); //getch(); free(r); Return NULL; }

no_tree *remover_1filho_left(no_tree *r) { no_arvore *aux = r->Esq; printf(" n number %d has been successfully removed! n", r->n); free(r); Return aux; }

no_tree *remover_1right_tree(no_tree *r) { no_tree *aux = r->dir; printf(" n number %d has been successfully removed! n", r->n); free(r); Return aux; }

no_tree *remover_2children(no_tree *r) { no_arvore *aux; int x; aux = menor_no_tree(r->dir); //helper receives the address of the smallest tree node. //printf("aux: %d n", aux->n); x = aux->n; //store the value of the helper in a variable x. r = remover_no_tree(r,x); //remove from the tree the node that will replace the node with 2 children.

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

}

//Function to check the type of node that will be removed. no_tree *remover_no(no_tree *r) { //Check if the node is a leaf (No children). if (r->dir == NULL && r->Esq == NULL) { //printf("O no %d eh uma folha. n", r->n); r = remover_sheet(r); } Else { if (r->dir == NULL) { //printf("No d has 1 child left. n", r->n); r = remover_1left(r); } Else { if (r->Esq == NULL) { //printf("No %d has 1 child to the right. n", r->n); r = remover_1right_child(r); } Else { //printf("No %d has 2 children. n", r->n); r = remover_2children(r); } } } Return; }

no_tree *remover_no_tree(no_tree *r, int x) { //Check that the tree is not empty. if (r != NULL) { //If the tree is not empty, fetch element x. if (r->n == x) ' //1 - Check if element x is in the root. //printf("FOUND!: %d n", r->n); r = remover_no(r); //Call the function to remove the node. } Else { //If x is not at the root, check which side x is at. if (x < r->n) { //Make recursive call to the left. r->Esq = remover_no_tree(r->Esq, x); } Else { //Make recursive call to the right. r->dir = remover_no_tree(r->dir, x); } r = balancing(r); //Check tree balance. } } Else { printf("Element not found: %d n", x); } Return; }

no_tree *insert random(no_tree *r){ int in a;

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_tree *r){ int in a;

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_tree *remover_no_tree random_tree(no_tree *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");

} insertion

     # 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>

Answer 1

Your problem is in removal with two children.

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;


}

See what your code is doing:

Notice that everything happened as it should, entertained on this line you are calling the removal function again:

r = remover_no_arvore(r,x); 

Now, the same tree from the first image is received, it checks that the root contains the desired element for removal, identifies that it has two children, searches the smallest in the right child, finds 500, calls the removal function to the number 500, identifies that it is the root element, identifies that it has two children, searches the smallest child on the right, finds 500, calls the removal function to the number 500, identifies that it is the root element, identifies that it has two children, searches the smallest child on the right, finds 500, calls removal to the number 500... ... ... ... ...

The problem is that you are correctly identifying the existence of two children, however you want to remove the smallest child from the right and the function highlighted above passes the value of the smallest child from the right to be removed and the same root or subtree is passed to this function.

Instead of:

r = remover_no_arvore(r,x); 

Try:

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

So you make sure that you want to remove the x element that is on the right of the tree, instead of passing the tree itself to remove the x element.

The problem you are having is an infinite recursion, as each function call creates a stack so that the program knows where it came from, creating endless stacks will generate the problem that, in English, is called Stackoverflow (stack overflow).

If this is correct, you came to the Stackoverflow site looking for a solution for Stackoverflow :D

Try to fix this and see if it worked.