Удаление бинарного дерева поиска (метод Inorder Pred) C ++

Question

Хорошо, я подумал, что это исправлено, но я получаю совершенно противоречивые результаты. Я переписал его с нуля, чтобы начать все заново, и вот мои результаты. Я не получаю ни ошибок, ни сбоев, просто они не удаляются. Это просто портит дерево, дает мне еще тонну листьев и все перемешивает. Не уверен, куда еще идти

template <class T>
void BST<T>::remove(struct Node<T>*& root, const T& x)
{
   Node<T>* ptr = root;
   bool found = false;
   Node<T>* parent;


   while (ptr != NULL && !found)
   {
       if (x < ptr->data)
       {
           parent = ptr;
           ptr = ptr->left;
       }
       else if (x > ptr->data)
       {
           parent = ptr;
           ptr = ptr->right;
       }
       else
           found = true;
   }

   if (found == false)
       return;
   else
   {
       if(ptr->left != NULL && ptr->right != NULL)
       {
           Node<T>* inOrderPtr = ptr->left;
           parent = ptr;
           while (inOrderPtr->right != NULL)
           {
               parent = inOrderPtr;
               inOrderPtr = inOrderPtr->right;
           }

           ptr->data = inOrderPtr->data;
           ptr = inOrderPtr;
       }
    Node<T>* subPtr = ptr->left;
    if (subPtr == NULL)
        subPtr = ptr->right;

    else if (parent->left == ptr)
        parent->left = subPtr;

    else
        parent->right = subPtr;

    delete ptr;
    }

Answer 1

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

if (root->data < x)
        remove(root->left, x);
    else 
        remove(root->right, x);

должно было быть

if(x < root->data)
remove(root->left, x);
else
remove(root->right, x);

Answer 2

Каждый T найден в дереве уникальным? Похоже, они из вашего кода ...

Похоже, это должно работать:

В другом случае удаление корневого узла:

Node<T> *tmp_r = root->left;
Node<T> *parent = root;
while (tmp_r->right != NULL)
{
    parent = tmp_r;
    tmp_r = tmp_r->right;
}
Node<T> *tmp_l = tmp_r;
while (tmp_l->left != NULL)
    tmp_l = tmp_l->left;

tmp_l->left = root->left;
tmp_r->right = root->right;
parent->right = NULL;

parent = root;
root = tmp_r;
delete parent;

Answer 3

Вы не должны вызывать remove() рекурсивно в третьем случае (где ваш комментарий "не уверен, что это правильно"). В случае, когда у удаляемого узла есть два дочерних элемента, вам нужно найти самого правого дочернего элемента левого дочернего элемента (как вы делаете; результирующий узел сохраняется в parent). У этого узла нет правого потомка - сделайте так, чтобы его правый потомок был правым потомком удаляемого узла. Затем просто измените переменную root на ее левого потомка; нет необходимости изменять элемент data в каких-либо узлах или вызывать remove рекурсивно.

В картинках:

Before:
         r  <- root points here
       /  \
      /    \
     a      b
    / \    / \
   x   c  y   y
      / \
     x   d
        /
       x

After:
      a    <-- root points here
     / \
    x   c
       / \
      x   d
         / \
        x   b
           / \
          y   y