Удаление элемента из дерева

@Vlast001 · Регистрация: 08.01.2019

Author24 — интернет-сервис помощи студентам

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

C++

template<class T>
inline Node<T>* Tree<T>::findMaxNode(Node<T>* node)
{
    while (node->GetRight()) {
        node = node->GetRight();
    }
    return node;
}
template<class T>
inline void Tree<T>::removeNode(Node<T>* delNode)
{
    if (delNode->GetLeft() && delNode->GetRight())
    {
        Node<T>* tmpMax = findMaxNode(delNode->GetLeft());
        delNode->SetData(tmpMax->GetData());
        removeNode(tmpMax);
        return;
    }
        *****
        delete[] delNode;

@oleg-m1973 · 06.08.2020, 20:01

Сообщение от Vlast001

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

C++

template<class T>
inline void Tree<T>::removeNode(Node<T>* delNode)
{
    if (!delNode->GetLeft() && !delNode->GetRight())
        delete[] delNode;
    else
    {
        Node<T>* tmpMax = findMaxNode(delNode->GetLeft());
        delNode->SetData(tmpMax->GetData());
        removeNode(tmpMax);
        return;
    }

И покажи структуру Node, а то что-то трудом могу представить, как можно реализовать removeNode(tmpMax)

@Vlast001 · 06.08.2020, 20:08 **[ТС]**

Сообщение от oleg-m1973

И покажи структуру Node

C++

template<class T>
class Node
{
    T data;
    Node<T>* left = nullptr;
    Node<T>* right = nullptr;
    Node<T>* parent = nullptr;
public:
    Node(T val);
    T GetData()const;
    Node<T>* GetParent()const;
    Node<T>* GetLeft()const;
    Node<T>* GetRight()const;
    
    void SetData(T val);
    void SetParent(Node<T>* val);
    void SetLeft(Node<T>* val);
    void SetRight(Node<T>* val);
};

Сообщение от oleg-m1973

if (!delNode->GetLeft() && !delNode->GetRight())
delete[] delNode;

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

C++

template<class T>
inline void Tree<T>::removeNode(Node<T>* delNode)
{
    if (delNode->GetLeft() && delNode->GetRight())
    {
        Node<T>* tmpMax = findMaxNode(delNode->GetLeft());
        delNode->SetData(tmpMax->GetData());
        removeNode(tmpMax);
        return;
    }
    else if (delNode->GetLeft())
    {
        if (delNode == delNode->GetParent()->GetLeft())
        {
            delNode->GetParent()->SetLeft(delNode->GetLeft());
        }
        else
        {
            delNode->GetParent()->SetRight(delNode->GetLeft());
        }
    }
    else if (delNode->GetRight())
    {
        if (delNode == delNode->GetParent()->GetRight())
        {
            delNode->GetParent()->SetLeft(delNode->GetRight());
        }
        else
        {
            delNode->GetParent()->SetLeft(delNode->GetRight());
        }
    }
    else 
    {
        if (delNode == delNode->GetParent()->GetLeft())
        {
            delNode->GetParent()->SetLeft( nullptr);
        }
        else
        {
            delNode->GetParent()->SetRight(nullptr);
        }
    }
    delete[] delNode;
}

Вообще я думал, что удаление можно и без рекурсии, но если и можно я не додумался
P.S.

C++

template<class T>
inline void Tree<T>::remove(T val)
{
    Node<T> * delNode = search(root, val);
    removeNode(delNode);
}

@oleg-m1973 · 06.08.2020, 20:35

Сообщение от Vlast001

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

Там не надо больше ничего делать. Если removeNode реализован правильно, то достаточно

C++

template<class T>
inline void Tree<T>::removeNode(Node<T>* delNode)
{
    if (!delNode->GetLeft() && !delNode->GetRight())
        removeNode(delNode);
    else
    {
        Node<T>* tmpMax = findMaxNode(delNode->GetLeft());
        delNode->SetData(tmpMax->GetData());
        removeNode(tmpMax);
        return;
    }
}

Добавлено через 5 минут
А вообще, вот так вот - delNode->SetData(tmpMax->GetData()), с деревом не работают. Там данные вообще не обязаны иметь конструкторы копирования/перемещения. Надо менять местами именно ноды, а не копировать их данные.

@Vlast001 · 06.08.2020, 20:36 **[ТС]**

Сообщение от oleg-m1973

правильно, то достаточно

Я заглючил, тобишь достаточно этого

C++

if (!delNode->GetLeft() && !delNode->GetRight())
        removeNode(delNode);
    else
    {
        Node<T>* tmpMax = findMaxNode(delNode->GetLeft());
        delNode->SetData(tmpMax->GetData());
        removeNode(tmpMax);
        return;
    }

и больше в методе ничего не нужно? никаких проверок типа else if(delNode->left){}else if(delNode->right){}...?
Я на этом сайте нарисовал свое дерево для визуализации https://www.cs.usfca.edu/~gall... n/BST.html
В общем до меня дошло, что все работало у меня правильно...Просто я накосячкил:

C++

else if (delNode->GetRight())
    {
        if (delNode == delNode->GetParent()->GetRight())
        {
            delNode->GetParent()->SetLeft(delNode->GetRight()); // вот, как видите я умудрился дважды SetLeft()написать, а тут SetRight() нужен
        }
        else
        {
            delNode->GetParent()->SetLeft(delNode->GetRight());
        }

Ну все как обычно..)

@oleg-m1973 · 06.08.2020, 20:38

Сообщение от Vlast001

и больше в методе ничего не нужно? никаких проверок типа else if(delNode->left){}else if(delNode->right){}...?

Ну да. Зачем их проверять, если ты не изменяешь ноду?

@Vlast001 · 06.08.2020, 20:50 **[ТС]**

Сообщение от oleg-m1973

Надо менять местами именно ноды, а не копировать их данные.

не совсем понял, ну с теорией у меня вроде как лады, а вот реализация..да и когда я изучал как люди реализовывают везде нечто такое вижу: node->data = node2->data; Ну так для примера(я конечно не отрицаю, что не очень много изучал как кто-то это реализовывал)
Так вот

Сообщение от oleg-m1973

если ты не изменяешь ноду

моя реализация терпимо или не оч?) И Вы имеете ввиду, что нужно написать некий Swap()? Но собственно как именно ноды местами поменять в дереве, куда parent`а пихать

Добавлено через 5 минут

Сообщение от oleg-m1973

template<class T>
inline void Tree<T>::removeNode(Node<T>* delNode)
{
if (!delNode->GetLeft() && !delNode->GetRight())
removeNode(delNode);
else
{
Node<T>* tmpMax = findMaxNode(delNode->GetLeft());
delNode->SetData(tmpMax->GetData());
removeNode(tmpMax);
return;
}
}

Я все-таки вставил это и закоментировал все остальное, произошла утечка памяти "с моим любимым кодом":завершает работу с кодом -1073741819.

@oleg-m1973 · 06.08.2020, 21:12

Сообщение от Vlast001

Я все-таки вставил это и закоментировал все остальное, произошла утечка памяти "с моим любимым кодом":завершает работу с кодом -1073741819.

Я ж вроде написал

Сообщение от oleg-m1973

Если removeNode реализован правильно, то достаточно

Сообщение от Vlast001

моя реализация терпимо или не оч?) И Вы имеете ввиду, что нужно написать некий Swap()? Но собственно как именно ноды местами поменять в дереве, куда parent`а пихать

Простейший вариант

C++

void ExtractNode(Node<T> *node, Node<T> *newNode = nullptr)
{
    if (!node->parent)
        return;
 
    if (node->parent->left == node)
        node->parent->left = newNode;
    else 
        node->parent->right = newNode;
}
 
template<class T>
void Tree<T>::removeNode(Node<T> *node)
{
    Node<T> *node2 = nullptr;
 
    if (node->right)
        node2 = findMinNode(node->right);
    else if (node->left)
        node2 = findMaxNode(node->left);
 
    if (node2)
    {
        ExtractNode(node2);
        node2->left = node->left;
        node2->right = node->right;
        ExtractNode(node, node2);
    }
 
    delete node;
}

Добавлено через 10 минут
Даже, наверное вот так (в любом случае не проверял)

C++

template<class T>
void Tree<T>::removeNode(Node<T> *node)
{
    if (!node->left)
        ExtractNode(node, node->right);
    else if (!node->right)
        ExtractNode(node, node->left);
    else
    {
        auto node2 = findMaxNode(node->left);
        ExtractNode(node2);
        node2->left = node->left;
        node2->right = node->right;
        ExtractNode(node, node2);
    }       
 
    delete node;
}

@Vlast001 · 07.08.2020, 15:54 **[ТС]**

Сообщение от oleg-m1973

Даже, наверное вот так (в любом случае не проверял)

Не работает))

Сообщение от oleg-m1973

void ExtractNode(Node<T> *node, Node<T> *newNode = nullptr)
{
if (!node->parent)
return;
if (node->parent->left == node)
node->parent->left = newNode;
else
node->parent->right = newNode;
}

Я пытался понять чем это отличается от того, что делал я но не понял, Вы просто для того, что я делал написали отдельную функцию

Сообщение от oleg-m1973

delete node;

Вы же имели ввиду delete[] node; ?)

@oleg-m1973 · 07.08.2020, 15:55

Сообщение от Vlast001

Вы же имели ввиду delete[] node; ?)

Конечно нет. Ты где-то делаешь new Node[N]?

@Vlast001 · 07.08.2020, 16:03 **[ТС]**

Сообщение от oleg-m1973

Ты где-то делаешь new Node[N]?

Нет, но это же указатель, сейчас я немного в замешательстве. Разве так безопасно?
Когда delete[] node идет очистка всей памяти на которую мог ссылаться указатель, разве будет тоже самое 1 в 1 при delete node?

@oleg-m1973 · 07.08.2020, 16:23

Сообщение от Vlast001

Когда delete[] node идет очистка всей памяти на которую мог ссылаться указатель, разве будет тоже самое 1 в 1 при delete node?

delete[] нужно вызывать только если ты выделял память при помощи new[]. Иначе просто delete

@Vlast001 · 07.08.2020, 16:45 **[ТС]**

Сообщение от oleg-m1973

только если ты выделял память при помощи new[]

Запомню.
Но блин почему это тогда пропускает компилятор да и работает так же? Наверное это великая тайна

@oleg-m1973 · 07.08.2020, 16:56

Сообщение от Vlast001

Но блин почему это тогда пропускает компилятор да и работает так же? Наверное это великая тайна

Компилятор, в compile-time, тебе ничего и не скажет - откуда он знает как ты выделял указатель, они все одинаковые. А в runtime просто упадёт.

https://wandbox.org/permlink/WmquKlkjieM69n1s

@Vlast001 30 / 14 / 7 Регистрация: 08.01.2019 Сообщений: 636
	07.08.2020, 16:03 [ТС]	11
	Сообщение от oleg-m1973 Ты где-то делаешь new Node[N]? Нет, но это же указатель, сейчас я немного в замешательстве. Разве так безопасно? Когда delete[] node идет очистка всей памяти на которую мог ссылаться указатель, разве будет тоже самое 1 в 1 при delete node? 0

@Vlast001 30 / 14 / 7 Регистрация: 08.01.2019 Сообщений: 636
	07.08.2020, 16:45 [ТС]	13
	Сообщение от oleg-m1973 только если ты выделял память при помощи new[] Запомню. Но блин почему это тогда пропускает компилятор да и работает так же? Наверное это великая тайна 0

@oleg-m1973 6579 / 4564 / 1843 Регистрация: 07.05.2019 Сообщений: 13,726
	07.08.2020, 16:56	14
	Сообщение от Vlast001 Но блин почему это тогда пропускает компилятор да и работает так же? Наверное это великая тайна Компилятор, в compile-time, тебе ничего и не скажет - откуда он знает как ты выделял указатель, они все одинаковые. А в runtime просто упадёт. https://wandbox.org/permlink/WmquKlkjieM69n1s 0

@oleg-m1973 6579 / 4564 / 1843 Регистрация: 07.05.2019 Сообщений: 13,726
	06.08.2020, 20:38	6
	Сообщение от Vlast001 и больше в методе ничего не нужно? никаких проверок типа else if(delNode->left){}else if(delNode->right){}...? Ну да. Зачем их проверять, если ты не изменяешь ноду? 0

@Vlast001 30 / 14 / 7 Регистрация: 08.01.2019 Сообщений: 636
	06.08.2020, 20:50 [ТС]	7
	Сообщение от oleg-m1973 Надо менять местами именно ноды, а не копировать их данные. не совсем понял, ну с теорией у меня вроде как лады, а вот реализация..да и когда я изучал как люди реализовывают везде нечто такое вижу: node->data = node2->data; Ну так для примера(я конечно не отрицаю, что не очень много изучал как кто-то это реализовывал) Так вот Сообщение от oleg-m1973 если ты не изменяешь ноду моя реализация терпимо или не оч?) И Вы имеете ввиду, что нужно написать некий Swap()? Но собственно как именно ноды местами поменять в дереве, куда parent`а пихать Добавлено через 5 минут Сообщение от oleg-m1973 template<class T> inline void Tree<T>::removeNode(Node<T>* delNode) { if (!delNode->GetLeft() && !delNode->GetRight()) removeNode(delNode); else { Node<T>* tmpMax = findMaxNode(delNode->GetLeft()); delNode->SetData(tmpMax->GetData()); removeNode(tmpMax); return; } } Я все-таки вставил это и закоментировал все остальное, произошла утечка памяти "с моим любимым кодом":завершает работу с кодом -1073741819. 0

@Vlast001 30 / 14 / 7 Регистрация: 08.01.2019 Сообщений: 636
	07.08.2020, 15:54 [ТС]	9
	Сообщение от oleg-m1973 Даже, наверное вот так (в любом случае не проверял) Не работает)) Сообщение от oleg-m1973 void ExtractNode(Node<T> node, Node<T> newNode = nullptr) { if (!node->parent) return; if (node->parent->left == node) node->parent->left = newNode; else node->parent->right = newNode; } Я пытался понять чем это отличается от того, что делал я но не понял, Вы просто для того, что я делал написали отдельную функцию Сообщение от oleg-m1973 delete node; Вы же имели ввиду `delete[] node;` ?) 0

@oleg-m1973 6579 / 4564 / 1843 Регистрация: 07.05.2019 Сообщений: 13,726
	07.08.2020, 15:55	10
	Сообщение от Vlast001 Вы же имели ввиду delete[] node; ?) Конечно нет. Ты где-то делаешь new Node[N]? 0

@oleg-m1973 6579 / 4564 / 1843 Регистрация: 07.05.2019 Сообщений: 13,726
	07.08.2020, 16:23	12
	Сообщение от Vlast001 Когда delete[] node идет очистка всей памяти на которую мог ссылаться указатель, разве будет тоже самое 1 в 1 при delete node? delete[] нужно вызывать только если ты выделял память при помощи new[]. Иначе просто delete 0