7
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>
In the remove function "child" you give free and then assign NULL? I believe an assignment is necessary, since it is only possible to know if it is at the end of the tree when the two children are NULL.
– João Sobral