Ошибки памяти при попытке сбалансировать двоичное дерево поиска? - PullRequest
Новая
       140

Ошибки памяти при попытке сбалансировать двоичное дерево поиска?

0 голосов
/ 31 марта 2020

У меня есть функция вставки для BST, которая также вызывает и проверяет, сбалансирован ли узел. Если это не так, я вызываю функцию вращения на узле. Вот в чем проблема -> до этого моя программа работала нормально, однако после добавления этой функции моя программа выдает ошибки. На данный момент я написал только функцию leftrotate, потому что я тестирую случай, который требует только поворота влево, поэтому, если сейчас есть повернуть направо, проблемы пока нет. Это моя функция вставки 

 Tnode* insertnode(Tnode* root, int key)
 {
   if (root == NULL)
    {
      Tnode* child = (Tnode*)malloc(sizeof(Tnode));
      child->left = NULL;
      child->right = NULL;
      child->key = key;
      child->balance = 0;
      return child;
    }
    if (root->key < key)
    {
      root->right = insertnode(root->right,key);
    }
    else if (root->key >= key)
    {
      root->left = insertnode(root->left,key);
    }
    if (balance(root) > 1 || balance(root)  < -1)
    {
      if (balance(root) == -2)
      {
        *edit* root = leftrotate(root);
      }
      else
      {
        //rightrotate(root);
      }
    }
    return root;
  }

Критерии баланса таковы: абсолютная разница между левым поддеревом и правым поддеревом узла не должна быть больше 1. Это моя функция левого поворота: 

 *edit*Tnode* leftrotate(Tnode *root)
 {
   Tnode * temproot = root;
   root = root->right;
   root->left = temproot;
   temproot->right = NULL;
   return root; *edit*
 }

Это функция, которая освобождает дерево: 

  void freetree(Tnode * root)
  {
    if(root == NULL)
    {
      return;
    }
    freetree(root->left);
    freetree(root->right);
    free(root);
    return;

Однако все блоки не освобождаются, и кажется, что дерево не сбалансировано правильно. Это отчет Valgrind: 

==3704== HEAP SUMMARY:
==3704==     in use at exit: 192 bytes in 8 blocks
==3704==   total heap usage: 11 allocs, 3 frees, 808 bytes allocated
==3704==
==3704== LEAK SUMMARY:
==3704==    definitely lost: 96 bytes in 4 blocks
==3704==    indirectly lost: 96 bytes in 4 blocks
==3704==      possibly lost: 0 bytes in 0 blocks
==3704==    still reachable: 0 bytes in 0 blocks
==3704==         suppressed: 0 bytes in 0 blocks
==3704== Rerun with --leak-check=full to see details of leaked memory
==3704==
==3704== For counts of detected and suppressed errors, rerun with: -v
==3704== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Что я делаю не так? Какие-нибудь советы? Редактировать: минимальный основной файл, который я открываю, является двоичным файлом. «i» относится к инструкции по вставке. 

      FILE *fp2 = fopen(argv[2],"rb");
      if (fp2 == NULL)
      {
        printf("%d\n",-1);
        return EXIT_FAILURE;
      }

      int key = 0;
      char placeh;
      Tnode * root = (Tnode*)malloc(sizeof(Tnode));
      fread(&root->key,sizeof(int),1,fp2);

      root->left = NULL;
      root->right = NULL;
      root->balance = 0;
      fread(&placeh,sizeof(char),1,fp2);
      while (1)
      {
        fread(&key,sizeof(int),1,fp2);
        fread(&placeh,sizeof(char),1,fp2);
        if (feof(fp2))
        {
          break;
        }
        if (placeh == 'i')
        {
          //printf("%d ",key);
          insertnode(root,key);
        }
      }
      printtree(root);
      freetree(root);
      fclose(fp2);
    }


    return EXIT_SUCCESS;
}
...