Ошибка Valgrind в освобождении дерева AVL

Question

Я создал дерево AVL для строк, и дерево само по себе хорошо работает: вставка, удаление, поиск - все работает хорошо. Однако, valgrind дает мне ошибку. Valgrind говорит, что ошибка в моей функции stringDuplicate (я сделал комментарий к определенному номеру строки, где valgrind указывает на это), и именно когда эта функция stringDuplicate вызывается моей функцией treeInsert (я сделал комментарий, где treeInsert вызывает stringDuplicate) , Может кто-нибудь помочь мне найти мою ошибку valgrind?

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdint.h> 
#include "tree.h" 

//NODES OF TREE 
struct node{ 
    char *word; 
    int balance; 
    struct node *children[2]; 
}; 

//STRUCT TREE WHICH CONTAINS A POINTER TO THE ROOT AND NUMBER OF ELEMENTS 
struct tree{ 
    struct node *root; 
    size_t numElements; 
}; 

//MALLOC SPACE FOR TREE 
struct tree *treeCreate(void){ 
    struct tree *s = malloc(sizeof(struct tree)); 
    s->root = NULL; 
    s->numElements = 0; 
    return s; 
} 

//CREATE A DUPLICATE OF THE STRINGS TO BE INSERTED/DELETED 
char *stringDuplicate (const char *s) { 
    char *d = malloc (strlen (s) + 1); //VALGRIND POINTS TO THIS LINE FOR ERROR 
    if (d == NULL) return NULL;   
    strcpy (d,s);       
    return d;        
} 

//RETURN THE SIZE OF THE TREE 
size_t treeSize(const struct tree *s){ 
    return s->numElements; 
} 

//CREATE A NEW NODE OF THE TREE 
struct node *make_node(char *word){ 
    struct node *temp = malloc(sizeof(struct node)); 

    if(temp != NULL){ 
     temp->word = word; 
     temp->children[0] = temp->children[1] = NULL; 
     temp->balance = 0; 
    } 

    return temp; 
} 

//CHANGE THE BALANCE OF NODE/NODES IN THE TREE 
void adjustBalance(struct node *root, int direction, int temp_bal){ 
    struct node *temp1 = root->children[direction]; 
    struct node *temp2 = temp1->children[!direction]; 

    if(temp2->balance == 0){ 
     root->balance = temp1->balance = 0; 
    }else if(temp2->balance == temp_bal){ 
     root->balance = -temp_bal; 
     temp1->balance = 0; 
    }else{ 
     root->balance = 0; 
     temp1->balance = temp_bal; 
    } 

    temp2->balance = 0; 
} 

//SINGLE ROTATION OF TREE 
struct node *singleRotation(struct node *root, int direction){ 
    struct node *temp = root->children[!direction]; 

    root->children[!direction] = temp->children[direction]; 
    temp->children[direction] = root; 

    return temp; 
} 

//DOUBLE ROTATION OF TREE 
struct node *doubleRotation(struct node *root, int direction){ 
    struct node *temp = root->children[!direction]->children[direction]; 

    root->children[!direction]->children[direction] = temp->children[!direction]; 
    temp->children[!direction] = root->children[!direction]; 
    root->children[!direction] = temp; 

    temp = root->children[!direction]; 
    root->children[!direction] = temp->children[direction]; 
    temp->children[direction] = root; 

    return temp; 
} 

//CHANGE THE BALANCE OF NODES WHEN INSERTING 
struct node *insertBalance(struct node *root, int direction){ 
    struct node *temp = root->children[direction]; 
    int temp_bal; 

    if(direction == 0){ 
     temp_bal = -1; 
    }else{ 
     temp_bal = 1; 
    } 

    if(temp->balance == temp_bal){ 
     root->balance = temp->balance = 0; 
     root = singleRotation(root, !direction); 
    }else{ 
     adjustBalance(root, direction, temp_bal); 
     root = doubleRotation(root, !direction); 
    } 

    return root; 
} 

//INSERT INTO TREE RECURSIVELY 
struct node *insertRecursive(struct node *root, char *word, int *flag){ 
    if(root == NULL){ 
     root = make_node(word); 
    } 
    else{ 
     //IF word < root->word, WE NEED TO GO LEFT AND direction < 0 
     //IF word > root->word, WE NEED TO GO RIGHT AND direction > 0 
     int direction = strcmp(word, root->word); 
     if(direction > 0){ 
      direction = 1; 
     }else if(direction < 0){ 
      direction = 0; 
     } 

     root->children[direction] = insertRecursive(root->children[direction], word, flag); 

     if(!*flag){ 
      if(direction == 0){ 
       root->balance += -1; 
      }else{ 
       root->balance += 1; 
      } 

      if(root->balance == 0){ 
       *flag = 1; 
      }else if(abs(root->balance) > 1){ 
       root = insertBalance(root, direction); 
       *flag = 1; 
      } 
     } 
    } 

    return root; 
} 

//SEARCH FOR A STRING IN TREE: 1 IF IN TREE, 0 IF NOT 
int searchTree(struct node *root, char *word){ 
    int flag = 0; 
    struct node *current = root; 
    while(!flag){ 
     if(current){ 
      int direction = strcmp(word, current->word); 
      if(direction == 0){ 
       flag = 1; 
       break; 
      }else if(direction > 0){ 
       direction = 1; 
      }else{ 
       direction = 0; 
      } 

      current = current->children[direction]; 
     }else{ 
      break; 
     } 
    } 

    return flag; 
} 

//INSERT NEW ELEMENT INTO TREE 
void treeInsert(struct tree *tree, const char *word){ 
    char *newWord = stringDuplicate(word); 
    int flag = searchTree(tree->root, newWord); 
    int temp = 0; 
    if(flag == 0){ 
     tree->root = insertRecursive(tree->root, newWord, &temp); 
     tree->numElements = tree->numElements + 1; 
    } 
} 

//CHANGE THE BALANCE OF NODES WHEN DELETING FROM TREE 
struct node *deleteBalance(struct node *root, int direction, int *flag){ 
    struct node *temp = root->children[!direction]; 
    int temp_bal; 
    if(direction == 0){ 
     temp_bal = -1; 
    }else{ 
     temp_bal = 1; 
    } 
    if(temp->balance == -temp_bal){ 
     root->balance = temp->balance = 0; 
     root = singleRotation(root, direction); 
    }else if(temp->balance == temp_bal){ 
     adjustBalance(root, !direction, -temp_bal); 
     root = doubleRotation(root, direction); 
    }else{ 
     root->balance = -temp_bal; 
     temp->balance = temp_bal; 
     root = singleRotation(root, direction); 
     *flag = 1; 
    } 

    return root; 
} 

//DELETE A STRING FROM TREE ITERATIVELY 
void treeDelete(struct tree *tree, const char *word){ 
    if(tree->root != NULL){ 
     char *newWord = stringDuplicate(word); 
     struct node *iterator, *ancestor_array[32]; 
     int ancestor_direction[32]; 
     int current_index = 0; 
     int flag = 0; 

     iterator = tree->root; 

     for(;;){ 
      if(iterator == NULL){ 
       return; 
      }else if(strcmp(newWord, iterator->word) == 0){ 
       tree->numElements = tree->numElements - 1; 
       break; 
      } 

      int direction = strcmp(word, iterator->word); 
      if(direction > 0){ 
       direction = 1; 
      }else if(direction < 0){ 
       direction = 0; 
      } 

      ancestor_direction[current_index] = direction; 
      ancestor_array[current_index++] = iterator; 

      iterator = iterator->children[ancestor_direction[current_index - 1]]; 
     } 

     if(iterator->children[0] == NULL || iterator->children[1] == NULL){ 
      int dir = iterator->children[0] == NULL; 

      if(current_index != 0){ 
       ancestor_array[current_index - 1]->children[ancestor_direction[current_index - 1]] = iterator->children[dir]; 
      }else{ 
       tree->root = iterator->children[dir]; 
      } 

      free(iterator); 
     }else{ 
      struct node *heir = iterator->children[1]; 
      ancestor_direction[current_index] = 1; 
      ancestor_array[current_index++] = iterator; 

      while(heir->children[0] != NULL){ 
       ancestor_direction[current_index] = 0; 
       ancestor_array[current_index++] = heir; 
       heir = heir->children[0]; 
      } 

      iterator->word = heir->word; 
      ancestor_array[current_index - 1]->children[ancestor_array[current_index - 1] == iterator] = heir->children[1]; 

      free(heir); 
     } 
     while(--current_index >= 0 && !flag){ 
      ancestor_array[current_index]->balance += ancestor_direction[current_index] != 0 ? -1 : 1; 

      if(abs(ancestor_array[current_index]->balance) == 1){ 
       break; 
      }else if(abs(ancestor_array[current_index]->balance) > 1){ 
       ancestor_array[current_index] = deleteBalance(ancestor_array[current_index], ancestor_direction[current_index], &flag); 

       if(current_index != 0){ 
        ancestor_array[current_index - 1]->children[ancestor_direction[current_index - 1]] = ancestor_array[current_index]; 
       }else{ 
        tree->root = ancestor_array[0]; 
       } 
      } 
     } 
    } 
    return; 
} 

//FREE TREE 
void treeDestroyHelper(struct node *root){ 
    if(root == NULL){ 
     return; 
    } 

    if(root->children[0] == NULL && root->children[1] == NULL){ 
     free(root->word); 
     free(root); 
    }else if(root->children[0] == NULL && root->children[1] != NULL){ 
     treeDestroyHelper(root->children[1]); 
     free(root->word); 
     free(root); 
    }else if(root->children[0] != NULL && root->children[1] == NULL){ 
     treeDestroyHelper(root->children[0]); 
     free(root->word); 
     free(root); 
    }else{ 
     treeDestroyHelper(root->children[0]); 
     treeDestroyHelper(root->children[1]); 
     free(root->word); 
     free(root); 
    } 
} 

//FREE TREE 
void treeDestroy(struct tree *s){ 
    treeDestroyHelper(s->root); 
    free(s); 
} 

редактировать: Просто хотел, чтобы добавить свой комментарий в случае, если кто-нибудь было интересно, что tree.h просто функциональные заголовки, которые я использую.

Answer 1

Вы дублируете word в treeDelete() и забудьте его освободить. Дублирование здесь не требуется. valgrind жалуется, что память, выделенная stringDuplicate(), не освобождена.

Кстати, это имя функции сбивает с толку, вы должны использовать treeDeleteString. То же самое для treeInsert ->treeInsertString и некоторые другие.

Edit: вы забыли освободить строку в treeDelete() перед тем free(iterator); и free(heir);. Я не могу сказать, правильна ли логика в treeDelete() из быстрого анализа вашего кода, но эти отсутствующие free() определенно заставляют память потеряться и сообщаться как таковой valgrind.