У меня проблема с отменой узла в моем двоичном дереве поиска. Метод, который я реализовал для исключения узла дерева, вместо этого удаляет все узлы, и я не понимаю, почему. Это класс узла:
#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;
}
Начните использовать отладчик. Что такое отладчик и как он может помочь мне диагностировать проблемы