Не могу узнать, как освободить () удаленные узлы в дереве AVL - PullRequest
Новая
       6

Не могу узнать, как освободить () удаленные узлы в дереве AVL

0 голосов
/ 03 апреля 2020

Проблема: при удалении узлов возникает утечка памяти. Это был недосмотр. Этот AVL может обрабатывать дубликаты узлов. 4 часа, и я не могу понять это. Сбои программы @ 8GB, когда информация уже должна была быть освобождена.

Я думаю, что мой лог c неисправен, и что я не должен удалять после остального. Я закомментировал return (T-> left).

Любые указатели относительно того, где освободить, были бы превосходными. 

typedef struct _AVL_node {
  char* key;
  char* value;
  struct _AVL_node *left, *right;
  int ht;
} _AVL_node;

_AVL_node * delete_node(_AVL_node *T,char* key, int* set_ret, char** ret_val, char** ret_val_key)
{
    _AVL_node *p;

    if(T==NULL)
    {
        return NULL;
    }
    else if(strcmp(key,T->key) > 0)     // insert in right subtree
    {
        T->right=delete_node(T->right,key,set_ret, ret_val,ret_val_key);

        if(BF(T)==2)
        {
            if(BF(T->left)>=0)
                T=LL(T);
            else
                T=LR(T);
        }
    }
    else if(strcmp(key,T->key) < 0)
    { 
        T->left=delete_node(T->left,key,set_ret,ret_val,ret_val_key);

        if(BF(T)==-2)   //Rebalance during windup
        {
            if(BF(T->right)<=0) 
                T=RR(T);
            else
                T=RL(T);
        }
    }
    else
    {
        // T to delete

        if (*set_ret == 1)
        {
            //printf("Deleted key,value: %s, %s\n", T->key, T->value);
            *ret_val = strdup(T->value);
            *ret_val_key = strdup(T->key);
        }
        *set_ret = 0;
        //data to be deleted is found
        if (T->right!=NULL)
        {
           //delete its inorder succesor

            p=T->right;

            while(p->left!= NULL)
                p=p->left;

            strcpy(T->key,p->key); 
            strcpy(T->value,p->value);
            T->right=delete_node(T->right,p->key,set_ret,ret_val,
                                                         ret_val_key);

            if (BF(T)==2)  //Rebalance during windup
            {
                if (BF(T->left)>=0)
                    T=LL(T);
                else
                    T=LR(T);
            }
        }
        else
        {
            _AVL_node* node = T->left;
            free(T);
            return(node);
            //return(T->left);
        }
    }
    T->ht=height(T);

    return(T);
}
...