Удаление узла листа BST

Question

Я пытаюсь реализовать дерево AVL только ради обучения. Мне удалось сделать ввод, но я застрял в деле удаления. У меня проблема с удалением листового узла (однопользовательский случай работает просто отлично). Проблема в том, что когда я удаляю узел, он не стирается из BST, вместо этого его значение просто превращается в 0, поэтому дерево никогда не выходит из равновесия при удалении узла. То, что я в основном делаю, это если я столкнулся с узлом без детей, я просто освобожу его. Вот код функции (без повторной балансировки части):

node_t *Delete (node_t *root, int num){ 

    if (!root){ 
    printf ("Not Found\n"); 
    return root; 
    } 

//=======Search for the Element============= 

    if (num > root->data) 
     Delete (root->right , num); 

    else if (num < root->data) 
     Delete (root->left , num); 

//======Delete element============== 

    else if (num == root->data){ 

    if (root->right && root->left){ //two child case 

     node_t *auxP = root->right; 

     while (auxP->left) //finding the successor 
      auxP=auxP->left; 

     root->data = auxP->data; 

     root->right = Delete (root->right, auxP->data);  
    } 

    else{ //one or no child 

     if (!root->right && !root->left){ // no childs 
      free(root);  
     } 
     else{ //one child 
      node_t *auxP = (root->right ? root->right : root->left); 
      *root=*auxP; 
      free(auxP); 
     }     
    } 

    } 
    return root; 
} 

Если у меня есть дерево, как это:

 10 
    /\ 
     5 15 
    /\ \ 
    2 6 17 

и я стараюсь, чтобы удалить 6, он заканчивается как этот

 10 
    /\ 
     5 15 
    /\ \ 
    2 0 17 

Это может быть очевидная ошибка, но я не могу ее найти. Любое объяснение того, почему он не работает, будет с благодарностью.

Answer 1

Когда вы удаляете узел, вам нужно изменить соответствующее дочернее поле его родителя. Но в вашем коде вы только передаете сам узел для удаления (node_t *root), чтобы родительский узел остался без изменений. В случае одного дочернего случая вы обходите его, копируя одиночный ребенок в узел-для-удаления и удаляйте только один дочерний элемент. Но в случае с листом вы ничего не делаете, чтобы исправить ссылку в родительском.

Один из способов заключается в том, чтобы каким-то образом передать родительский узел таким образом, чтобы, когда узел-к-удалению является листом, разорвать связь с родителем и установить соответствующий дочерний элемент родителя на NULL.

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