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

Question

Я пытаюсь написать удаление из двоичной функции дерева. Я немного потерян, поэтому я пытаюсь обрабатывать его в каждом случае, начиная с того, что значение, которое я пытаюсь удалить, находится в корне BST. Чтобы проверить мою функцию, я сначала вызываю функцию printcontents(), которая печатает все содержимое дерева, а затем я вызываю remove (8) [8, являющееся значением в моем корне в данный момент), а затем вызов printcontents () еще раз. То, как я это делаю, - это попытаться заменить корень «самым правым» значением в левой части дерева. Когда я вызываю printcontents во второй раз, он правильно печатает новое значение корня, но когда он продолжает печатать содержимое и достигает точки, в которой это значение было, оно имеет случайное длинное число «-572 ......» (хотя я не думаю, что это имеет значение), а затем моя программа вылетает. Я вижу, что значение моего корня заменяется, но что происходит потом?

Вот моя удалить функции:

void BinarySearchTree::remove(int value) { 

     Node* tmp = head; 
     Node* tmp2 = head; 


    if (head->data == value && head->left != NULL) { 

     tmp=tmp->left; 

     while (tmp->right != NULL) { 
      tmp=tmp->right; 

     } 

     while (tmp2->right->right != NULL) { 
      tmp2=tmp2->right; 

     } 

     if (tmp->left == NULL) {  

     head->data = tmp->data; 
     tmp2->right = NULL; 
     delete tmp; 

     } 

     if (tmp->left != NULL) { 

      head->data = tmp->data; 
      tmp2->right = tmp->left; 
      delete tmp; 

     } 




} 

Это явно неполным, но я тестирую его обрабатывать только случай, в котором корень удаляется и заменяется на самый правый значение в левой части дерево (если есть левая сторона, что есть), и я чувствую, что логически он должен работать, поэтому, возможно, это когда я «удаляю tmp», что все идет не так. Я не знаю, нужна ли моя вся программа, но если да, то дайте мне знать!

Answer 1

Могу ли я предположить, что вместо того, чтобы писать для root, почему вы не рассматриваете дело так, как это описано в CLRS: Это два разных случая. 1. Когда удаляемый узел является листом 2. Когда удаляемый узел не является листовым (в этом случае замените его преемником/предшественником).

Корневое удаление, очевидно, подпадает под второй случай. Это всего лишь предложение.