У меня проблема с отменой узла в моем двоичном дереве поиска. Метод, который я реализовал для исключения узла дерева, вместо этого удаляет все узлы, и я не понимаю, почему. Это класс узла:
#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(), и теперь он работает нормально!
Ожидаете ли вы, что Nodo<T> *tmp = new Nodo<T>(x); найдет узел, содержащий x внутри дерева? Это не так. Почему именно transplant() заменяет корень radice?
Примечание: прочтите правило трёх/пяти/нуля.
У меня правильный Nodo<T> *tmp = new Nodo<T>(x) с Nodo<T> *tmp = search(x) и это работает! (Теперь я изменю ответ, вставив метод поиска). В transplant я заменяю корень узлом v, когда у пересаживаемого узла нет родителей, это означает, что это корень. Но я не понимаю, почему оно раньше удалило все узлы? Спасибо, что дали мне это предложение!
Вы также можете рассмотреть возможность создания Nodo частной детали реализации BinarySearchTree. Тогда вам не придется проделывать много работы по инкапсуляции деталей реализации.
Спасибо, это очень хорошая идея, я не подумал об этом, когда начинал эти упражнения.
Примечание: внутри класса повторение аргумента шаблона не является обязательным. Внутри класса Nodo вы можете писать такие вещи, как Nodo<T>* sx;, но большинство программистов предпочитают Nodo* sx;. Кроме того, рекомендуется использовать инициализаторы членов по умолчанию, например: Nodo* sx{ nullptr };
К вашему сведению, синтаксис this-> вам не нужен. Попробуйте удалить его и посмотрите, что произойдет.
Ваша процедура поиска ищет все левые или все правые ветви. Он не может найти внутренние узлы. Ему также нужен какой-то способ сигнализировать о неудачном поиске. 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, чтобы избежать утечек памяти.





С внесенными вами изменениями ваша функция 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
}
Когда ваш класс заработает, вам следует добавить несколько функций «Правила пяти», чтобы вы могли копировать, перемещать и назначать деревья без утечки памяти или запуска двойного удаления.
Спасибо, вчера мне пришлось в спешке добавить функцию поиска, поэтому я кое-что упустил. Вы очень хорошо объяснили, в чем суть, спасибо, сегодня днём изменю код.
Метод поиска в вашем текущем классе 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;
}
Начните использовать отладчик. Что такое отладчик и как он может помочь мне диагностировать проблемы