Удаление корневого узла дерева двоичного поиска
У меня есть эта функция для удаления узла в бинарном дереве поиска, которое, кажется, работает, КРОМЕ в случае, когда я прошу его удалить корневой узел. Предполагается, что он принимает самое правое значение слева и заменяет узел этим; однако, как только это происходит, дочерние указатели нового корневого узла, кажется, не указывают на дочерние узлы исходного корневого узла. Код выглядит следующим образом:
bool delete_node(Node*& root, TYPE data) {
Node* toDelete;
Node* parent;
// This function is defined appropriately elsewhere, and finds the target to be deleted
toDelete = find(data, root);
if (!toDelete) {
return false;
}
// This function is defined appropriately elsewhere, and finds the parent of the node to be deleted
parent = find_parent(root, toDelete);
// Other cases left out because they work
// If the target node has two children:
if (toDelete->left && toDelete->right)
{
// find rightmost child on left that is a leaf
Node *replacement = toDelete->left;
while (replacement->right)
{
replacement = replacement->right;
}
// set the target node's data
toDelete->data = replacement->data;
if (parent)
{
if ( parent->data < toDelete->data )
{
parent->right = replacement;
} else
{
parent->left = replacement;
}
} else
{
// if node has no parents, then it is the root and should be replaced with replacement
// This line here is what seems to be causing my trouble...I think
root = replacement;
}
parent = find_parent(toDelete, replacement);
if (parent)
{
if (parent->left == replacement)
parent->left = NULL;
else
parent->right = NULL;
}
delete toDelete;
return true;
}
}
Заранее спасибо!
Решение
то, что я закончил, было следующим: отслеживать родительский узел, который находится над узлом, который заменяет удаляемый узел. Затем необходимо рассмотреть 2 случая: родитель — это узел, который нужно удалить, а родитель — это не узел, который нужно удалить. при замене соответствующих частей дерева в правильном случае структура и инварианты дерева остались в порядке, а удаляемый узел был успешно удален. технически это были бы данные на узле, который нужно удалить.
else if (toDelete->left != NULL && toDelete->right != NULL) {
// find rightmost child on left that is a leaf
Node* replacement = toDelete->left;
parent = toDelete;
// parent is now the parent of the replacement
while ( replacement->right ) {
parent = replacement;
replacement = replacement->right;
} // By the end, parent will be the node one above replacement
toDelete->key = replacement->key;
if (parent == target)
parent->left = replacement->left;
else
parent->right = replacement->left;
delete replacement;
return true;
}
Другие решения
Это то, что я сделал, чтобы это сработало. Просто проверьте, является ли этот узел корневым, и если да, установите новый корень. Ниже приведен рабочий код, который у меня есть. Три места, отмеченные звездочками, — это то, что я добавил, чтобы все заработало. Все остальные строки кода — просто стандартная теория учебника.
inline NamesBinaryTree::Node* NamesBinaryTree::Node::removeNode (Node*& node, const Female* female, stringComparisonFunction s) { // Taken from p.253 of Alex Allain's "Jumping Into C++".
if (!node)
return nullptr;
if (node->femaleInfo.first == female->getName()) {
if (!node->left) { // i.e. node has either one child or zero children.
Node* rightNode = node->right;
if (node->isRoot()) // ***
namesBinaryTree.setRoot(rightNode); // Tested to work correctly. Note that we cannot call 'delete node;', since that will delete the very root that we are setting!
else
delete node;
return rightNode; // This will return nullptr if node->right is also nullptr, which is what we would want to do anyway since that would mean that node has zero children.
}
if (!node->right) { // i.e. node has exactly one child, namely its left child, in which case return that left child.
Node* leftNode = node->left;
if (node->isRoot()) // ***
namesBinaryTree.setRoot(leftNode);
else
delete node;
return leftNode; // This will never be nullptr, else the previous if condition would have been met instead.
}
Node* maxNode = findMaxNode(node->left); // node has two children, so it shall be replaced by the largest valued node in its left subtree.
maxNode->left = removeMaxNode(node->left, maxNode); // Note that maxNode->left = node->left is not enough because without actually removing maxNode, the node that was pointing to maxNode will now be pointing to maxNode in its new position (and the subtree under it), and the subtree that was under maxNode will now be gone.
maxNode->right = node->right;
if (node->isRoot()) // ***
namesBinaryTree.setRoot(maxNode); // Tested to work correctly.
else
delete node;
return maxNode;
}
else {
const int result = (*s)(female->getName(), node->femaleInfo.first);
if (result < 0)
node->left = removeNode(node->left, female, s); // This assignment can only work if node is passed by reference (hence the parameter Node*& node), at least this is what "C++ Essentials" did in their solution, p.247.
else // Don't use 'else if (result > 0)'. Let the equality case be covered here too (just as in NamesBinaryTree::Node::insertNode).
node->right = removeNode(node->right, female, s); // Again, this assignment can only work if node is passed by reference (hence the parameter Node*& node).
}
return node; // So if node->femaleInfo.first != female->getName(), then the same node is returned, which means that the two assignment lines above don't change any values.
}