Удаление в бинарном дереве поиска

Question

Поэтому, когда я удаляю в бинарном дереве поиска, мне нужно иметь как 7 разных случаев, например:

1. Левый лист;
2. Правый лист;
3. Левыйребенок только с оставленным ребенком.// т.е. удаляемый узел является левым дочерним элементом своего родителя, и у него есть только левый дочерний элемент.
4. Левый дочерний элемент с единственным правым дочерним элементом.
5. Правый дочерний элемент с единственным левым дочерним элементом.
6. Правый потомок с единственным правым потомком.
7. У удаляемого узла есть оба потомка, то есть правый и левый.

Теперь, когда этот код использует if-else, он получаетдовольно неприятно .. есть ли другой способ сделать это.

Вот мой фрагмент кода

if(current->left==NULL && current->right==NULL && current->key<prev->key)   //left leaf
prev->left=NULL;
else if(current->left==NULL && current->right==NULL && current->key>prev->key) // right     leaf
prev->right=NULL;
else if(current->left!=NULL && current->right==NULL && current->key<prev->key) // left     child with one child
prev->left=current->left;
else if(current->left==NULL && current->right!=NULL && current->key<prev->key)
prev->left=current->right;
else if(current->left!=NULL && current->right==NULL && current->key>prev->key)
prev->right=current->left;
else if(current->left==NULL && current->right!=NULL && current->key>prev->key)
prev->right=current->left;
else if(current->left!=NULL && current->right!=NULL)
{
    check=current->right;
    check1=check;
    while(check->left!=NULL)
    {
    check1=check;
    check=check->left;
    }
    *current=*check;
    check1->left=NULL;
}

Answer 1

Вы можете сделать это намного проще и просто ограничить себя тремя случаями при удалении узла из BST (дерево двоичного поиска):

1. узел без дочерних элементов (лист): просто удалите его - ничего особенного делать не нужно
2. узел с одним дочерним элементом: удалите его и переместите дочерний элемент на его место
3. узел с двумя дочерними элементами: замените его предшественником или преемником по порядку, а затем удалите его

Страница вики содержит пример того, как это может выглядеть в коде.

Или как очень простой пример в C:

if (current->left==NULL && current->right==NULL) {
    /* leaf node */
    bst_replace(current, NULL);
}
else if (current->left==NULL || current->right==NULL) {
    /* node with one child */
    bst_replace(current, ((current->left) ? current->left : current->right));
}
else {
    /* node with two children */
    Node* successor = bst_next(current);
    current->data = successor->data;
    bst_replace(successor, successor->right);
}

Answer 2

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

Но просто сделать код простым.Вы можете сделать что-то вроде этого:

bool b1 = (current->left == NULL);
bool b2 = (current->right == NULL);
bool b3 = (current->key > prev->key);

int decision_case = b1 * 4 + b2 * 2 + b3;

switch(decision_case) {
  case 0: // fill in code here
          break;
  ...
  ...
  case 7: // fill in code here
          break;
}

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

Answer 3

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

delete current->left;
delete current->right;