Удаление двоичного дерева дерева поиска

Question

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

Это моя последняя попытка:

Node* RBT::BST_remove(int c) 
{ 
    Node* t = get_node(c); 
    Node* temp = t; 

    if(t->get_left() == empty) 
     *t = *t->get_left(); 
    else if(t->get_right() == empty) 
     *t = *t->get_right(); 
    else if((t->get_left() != empty) && (t->get_right() != empty)) 
    { 
     Node* node = new Node(t->get_data(), t->get_parent(), t->get_colour(), t->get_left(), t->get_right()); 
     *t = *node; 
    } 

    return temp; 
} 

Node* RBT::get_node(int c) 
{ 
    Node* pos = root; 

    while(pos != empty) 
    { 
     if(c < pos->get_data()) 
      pos = pos->get_left(); 
     else if(c == pos->get_data()) 
      return pos; 
     else 
      pos = pos->get_right(); 
    } 

    return NULL; 
} 

т является узлом и пустым просто узел с чем в нем.

Я просто пытаюсь поменять значения, но получаю ошибку времени выполнения. Есть идеи?

Редактировать: Я возвращаю temp, чтобы удалить его впоследствии.

Благодаря

Answer 1

Во-первых, ваш последний else if условный пункт является излишним. Поменяйте его на else.

Во-вторых, я думаю, что это облегчит вам задачу, если вы укажете в качестве параметра указатель на удаляемый узел. Вы можете написать функцию find(), которая найдет узел с его ключевым ключом. Я предполагаю, конечно, что вы можете изменить подпись функции. Если вы можете взять в качестве параметра узел для удаления, вы можете сосредоточиться на удалении узла, а не на добавлении логики для поиска узла. В противном случае еще напишите, что функция find() и используйте это для получения указателя на соответствующий узел.

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

1. Узел удаления не имеет детей. Это просто: просто отпустите свои ресурсы, и все готово.
2. Узел имеет единственный дочерний узел. Это тоже довольно просто. Отпустите узел и замените его своим дочерним элементом, чтобы ребенок удерживал место удаленного узла в дереве.
3. У узла есть двое детей. Назовем узел D. Найдите самый правый ребенок из левого поддерева D. Назовем этот узел R. Назначьте значение R в D и удалите R (как описано в этом алгоритме). Обратите внимание, что R может иметь ноль или один ребенок.

Третий сценарий, показанный:

  . 
     . 
     . 
    /
    D 
    /\ 
    /\ . 
/\ 
/ \ 
+------+ 
     \ 
     R 
     /
     ?