Метод удаления двоичного дерева поиска удаляет все узлы, а не только выбранный C++

У меня проблема с отменой узла в моем двоичном дереве поиска. Метод, который я реализовал для исключения узла дерева, вместо этого удаляет все узлы, и я не понимаю, почему. Это класс узла:

#include <iostream>

using namespace std;

template <class T>
class Nodo {
private:
    T val;
    Nodo<T> *sx;
    Nodo<T> *dx;
    Nodo<T> *padre;
public:
    explicit Nodo(T x) {
        this->val = x;
    }
    void setVal(T y) {
        this->val = y;
    }
    T getVal() {return this->val;}

    void setPadre(Nodo<T> *x) {
        this->padre = x;
    }

    Nodo<T> *getPadre() {
        return this->padre;
    }

    void setSx(Nodo<T> *n) {
        this->sx = n;
    }

    void setDx(Nodo<T> *n) {
        this->dx = n;
    }

    Nodo *getSx() {return this->sx;}
    Nodo *getDx() {return this->dx;}
};

Существует класс BST со всеми методами:

template <typename T>
class BinarySearchTree {
private:
    Nodo<T> *radice;
public:
    BinarySearchTree() {
        radice = nullptr;
    }
    void insert(T x) {
        Nodo<T>* tmp = new Nodo<T>(x);
        Nodo<T> *supp = nullptr;
        Nodo<T> *radix = radice;
        tmp->setSx(nullptr);
        tmp->setDx(nullptr);

        while (radix != nullptr) {
            supp = radix;
            if (x < radix->getVal()) {
                radix = radix->getSx();
            } else {
                radix = radix->getDx();
            }
        }
        tmp->setPadre(supp);
        if (supp == nullptr) {
            radice = tmp;
        } else if (x < supp->getVal()) {
            supp->setSx(tmp);
        } else {
            supp->setDx(tmp);
        }
    }

    void _inorder(Nodo<T> *prova) {
        if (prova != nullptr) {
            _inorder(prova->getSx());
            cout << prova->getVal() << " ";
            _inorder(prova->getDx());
        }
    }

    void inorder() {
        _inorder(radice);
        cout << "----" << endl;
    }

    Nodo<T> *minimum(Nodo<T>* x) {
        Nodo<T> *min = x;
        while (min->getSx() != nullptr)
            min = min->getSx();
        return min;
    }

    Nodo<T> *search(T x) {
        Nodo<T> *iter = radice;
        if (x < iter->getVal()) {
            while (iter->getVal() != x)
                iter = iter->getSx();
            return iter;
        } else {
            while (iter->getVal() != x)
                iter = iter->getDx();
            return iter;
        }
    }
    
    void transplant(Nodo<T> *u, Nodo<T> *v) {
        if (u->getPadre() == nullptr) {
            radice = v;
        } else if (u == u->getPadre()->getSx()) {
            u->getPadre()->setSx(v);
        } else {
            u->getPadre()->setDx(v);
        }
        if (v != nullptr)
            v->setPadre(u->getPadre());
    }


    void delTree(T x) {
        Nodo<T> *tmp = search(x);
        Nodo<T> *supp = nullptr;
        if (tmp->getSx() == nullptr)
            transplant(tmp, tmp->getDx());
        else if (tmp->getDx() == nullptr)
            transplant(tmp, tmp->getSx());
        else {
            supp = minimum(tmp->getDx());
            if (supp->getPadre() != tmp) {
                transplant(supp, supp->getDx());
                supp->setDx(tmp->getDx());
                supp->getDx()->setPadre(supp) ;
            }
            transplant(tmp, supp);
            supp->setSx(tmp->getSx());
            supp->getSx()->setPadre(supp);
        }
    }
};


int main() {
    BinarySearchTree<int> bst;
    bst.insert(30);
    bst.insert(10);
    bst.insert(50);
    bst.insert(2);
    bst.inorder();
    bst.delTree(2);
    bst.inorder();
}

Теперь, когда я вызываю метод delTree с любым узлом, он удаляет все узлы. Может ли кто-нибудь помочь мне понять, где ошибка в коде? Спасибо!

Обновлено: я добавил метод search() в класс BST и изменил назначение tmp в методе delTree(), и теперь он работает нормально!

Начните использовать отладчик. Что такое отладчик и как он может помочь мне диагностировать проблемы

user12002570 27.08.2024 16:34

Ожидаете ли вы, что Nodo<T> *tmp = new Nodo<T>(x); найдет узел, содержащий x внутри дерева? Это не так. Почему именно transplant() заменяет корень radice?

Quimby 27.08.2024 16:53

Примечание: прочтите правило трёх/пяти/нуля.

Chris 27.08.2024 17:00

У меня правильный Nodo<T> *tmp = new Nodo<T>(x) с Nodo<T> *tmp = search(x) и это работает! (Теперь я изменю ответ, вставив метод поиска). В transplant я заменяю корень узлом v, когда у пересаживаемого узла нет родителей, это означает, что это корень. Но я не понимаю, почему оно раньше удалило все узлы? Спасибо, что дали мне это предложение!

NinoQuindici_Git 27.08.2024 17:01

Вы также можете рассмотреть возможность создания Nodo частной детали реализации BinarySearchTree. Тогда вам не придется проделывать много работы по инкапсуляции деталей реализации.

Chris 27.08.2024 17:17

Спасибо, это очень хорошая идея, я не подумал об этом, когда начинал эти упражнения.

NinoQuindici_Git 27.08.2024 17:21

Примечание: внутри класса повторение аргумента шаблона не является обязательным. Внутри класса Nodo вы можете писать такие вещи, как Nodo<T>* sx;, но большинство программистов предпочитают Nodo* sx;. Кроме того, рекомендуется использовать инициализаторы членов по умолчанию, например: Nodo* sx{ nullptr };

tbxfreeware 27.08.2024 17:25

К вашему сведению, синтаксис this-> вам не нужен. Попробуйте удалить его и посмотрите, что произойдет.

Thomas Matthews 27.08.2024 18:15

Ваша процедура поиска ищет все левые или все правые ветви. Он не может найти внутренние узлы. Ему также нужен какой-то способ сигнализировать о неудачном поиске. void example() { BinarySearchTree<int> bst; bst.insert(0); bst.insert(2); bst.insert(1); bst.insert(3); bst.inorder(); bst.delTree(1); bst.inorder(); bst.delTree(100); bst.inorder(); } После удаления необходимо вызвать оператору delete, чтобы избежать утечек памяти.

tbxfreeware 27.08.2024 21:43
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
9
72
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

С внесенными вами изменениями ваша функция delTree выглядит хорошо. Однако проблемы с функцией search привели к ее сбою, когда я запустил следующий пример.

void example() {
    BinarySearchTree<int> bst;
    bst.insert(0);
    bst.insert(2);
    bst.insert(1);
    bst.insert(3);
    bst.inorder();
    bst.delTree(1);
    bst.inorder();
    bst.delTree(100);
    bst.inorder();
}

Исключение, возникающее по адресу 0x00007FF733062C47 в StackOverflow.exe: 0xC0000005: местоположение чтения нарушения прав доступа 0x0000000000000000.

Исключение было выдано при выполнении второго цикла процедуры поиска.

Nodo<T>* search(T x) {
    Nodo<T>* iter = radice;
    if (x < iter->getVal()) {
        while (iter->getVal() != x)
            iter = iter->getSx();
        return iter;
    }
    else {
        while (iter->getVal() != x)
            iter = iter->getDx();  // <--------------- Access violation
        return iter;
    }
}

Очевидно, переменная iter имела значение nullptr, а затем была разыменована.

Глядя на код, вы можете увидеть, что произошло. Цикл спускается по правой стороне дерева в поисках x, а когда ему не удается его найти, iter получает nullptr.

И это другая проблема. Когда x лежит в левой половине дерева, search проверяет только левого дочернего элемента каждого узла. Аналогично, когда x находится в правой половине дерева, search сканирует только правые дочерние узлы.

Обе проблемы можно решить, используя рекурсивный поиск.

Nodo<T>* search(T const x)
{
    // Search the tree for a node with the value `x`.
    // If found, return a pointer to the node.
    // If `x` is not in the tree, return `nullptr`.
    return search(x, radice);
}
Nodo<T>* search(T const x, Nodo<T>* const ptr)
{
    if (!ptr) return nullptr;
    if (x == ptr->getVal()) return ptr;
    if (x < ptr->getVal()) return search(x, ptr->getSx());
    return search(x, ptr->getDx());
}

Когда функция search терпит неудачу, поскольку x нет в дереве, она возвращает nullptr. Вам нужно проверить это в верхней части функции delTree.

void delTree(T x) {
    Nodo<T>* tmp = search(x);
    if (tmp == nullptr) return;
    //...
}

Как избежать утечек памяти

После удаления узла из дерева следует вызвать на нем оператор delete. В противном случае ваша программа потеряет память. Я добавил вызов прямо в конце функции delTree.

void delTree(T x) {
        // ...
        transplant(tmp, supp);
        supp->setSx(tmp->getSx());
        supp->getSx()->setPadre(supp);
    }
    delete tmp;  <-------------- Avoid memory leaks
}

Когда ваш класс заработает, вам следует добавить несколько функций «Правила пяти», чтобы вы могли копировать, перемещать и назначать деревья без утечки памяти или запуска двойного удаления.

Спасибо, вчера мне пришлось в спешке добавить функцию поиска, поэтому я кое-что упустил. Вы очень хорошо объяснили, в чем суть, спасибо, сегодня днём изменю код.

NinoQuindici_Git 28.08.2024 14:11

Метод поиска в вашем текущем классе BST не обрабатывает угловой случай: если x равен значению в текущем итере, он заранее решает, в какой ветке искать, на основе корневого значения.

Nodo<T> *search(T x) {
    Nodo<T> *iter = radice;
    if (x < iter->getVal()) {
        while (iter->getVal() != x)
            iter = iter->getSx();
        return iter;
    } else {
        while (iter->getVal() != x)
            iter = iter->getDx();
        return iter;
    }
}

Что вы можете реализовать методом поиска для обработки общего случая:

Nodo<T> *search(T x) {
    Nodo<T> *iter = radice;
    while (iter != nullptr && iter->getVal() != x) {
        if (x < iter->getVal()) {
            iter = iter->getSx();
        } else {
            iter = iter->getDx();
        }
    }
    return iter;
}

Другие вопросы по теме