Как удалить узел в двоичном дереве поиска с помощью рекурсии

Question

Теперь я пытаюсь сформулировать функцию удаления для удаления узла внутри двоичного дерева поиска, учитывая, что узел содержит искомое содержимое. Я написал скелет для функции, выполняющей поиск содержимого, и возвращает true или false в зависимости от того, нашел ли он это или нет. Проблема в том, что я не могу понять, как реализовать фактическую часть удаления для моей функции. Если корневой узел содержит значение, которое я ищу, я не знаю, как назначить одному из старых корневых корней положение корня после удаления. Мне также трудно определить, как NULL указать указатели на детей после удаления узла и повторные части дерева, которые можно было бы разделить, если я просто отключу узел, содержащий искомое значение.

Ниже функция у меня до сих пор:

bool BSTree::Remove(int content, BSTNode*& bst_node) const { 
// makes sure the tree is not empty (function returns false if it is) 
if (bst_node != NULL) { 
    // checks to see if nodes contents matches content param 
    if (bst_node->GetContents() == content) { 
     // checks to see if the node has children 
     if (bst_node->GetLeftChild() == NULL && bst_node->GetRightChild() == NULL) { 

     } else if (bst_node->GetLeftChild() == NULL) { 

     } else if (bst_node->GetRightChild() == NULL) { 

     } else { 

     } 
     return true; 
    // checks to see if the content of node is less/greater than content param 
    } else if (content < bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() != NULL) 
      return Remove(content, bst_node->GetLeftChild()); 
    } else if (content > bst_node->GetContents()) { 
     if (bst_node->GetRightChild() != NULL) 
      return Remove(content, bst_node->GetRightChild()); 
    } 
    } 
    return false; 
} 

Что я добавил:

bool BSTree::Remove(int content, BSTNode*& bst_node) { 
    BSTNode* parent = bst_node; 
    if (bst_node == NULL) { 
    return false; 
    } else { 
    if (content == bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() == NULL && bst_node->GetRightChild() == NULL) { 
     if (bst_node == root_) { 
      Clear(); 
     } else { 
      // code for deleting leaf 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      size_--; 
     } 
     } else if (bst_node->GetLeftChild() == NULL) { 
     // code for deleting node with only right child 
     if (bst_node == root_) { 
      parent = bst_node->GetRightChild(); 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      root_ = parent; 
     } else { 

     } 
     size_--; 
     } else if (bst_node->GetRightChild() == NULL) { 
     // code for deleting node with only left child 
     if (bst_node == root_) { 
      parent = bst_node->GetLeftChild(); 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      root_ = parent; 
     } else { 

     } 
     size_--; 
     } else { 
     // code for deleting node with two children 
     size_--; 
     } 
    } else if (content < bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() == NULL) { 
     return false; 
     } else { 
     return Remove(content, bst_node->GetLeftChild()); 
     } 
    } else if (content > bst_node->GetContents()) { 
     if (bst_node->GetRightChild() == NULL) { 
     return false; 
     } else { 
     return Remove(content, bst_node->GetRightChild()); 
     } 
    } 
    } 
    return true; 
} 

функцию Helper для функции REMOVE:

int BSTree::FindMin(BSTNode* bst_node) const { 
    if (bst_node != NULL) { 
    if (bst_node->GetLeftChild() != NULL) 
     return FindMin(bst_node->GetLeftChild()); 
    return bst_node->GetContents(); 
    } 
    return 0; 
} 

Answer 1

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

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

Обычная реализация, используемая для дерева двоичного поиска, состоит в том, чтобы сделать Remove возвратом узла, поэтому вы можете изменить дерево, просто вернув узлы, и не нужно беспокоиться о делах внуков.