How to overloading operator= in red-black tree? C++

Question

I have a red-black tree that needs to be overloaded with an assignment operator. I kind of overloaded the operator= of a binary tree whose nodes don't know their parents. But how do I do this for a tree where nodes have a relationship with the left, right, and parent?

template<typename KEY, typename VALUE> class map;
template <typename KEY, typename VALUE>
class Node
{
private:
    friend class map<KEY, VALUE>;
 
    KEY id;
    VALUE object;
    bool color;
 
    Node* parent;
    Node* left;
    Node* right;
 
    Node(): id(0), object(nullptr), color(RED), parent(nullptr), left(nullptr), right(nullptr) {}
    Node(const KEY& id, const VALUE& object) : id(id), object(object), color(RED), parent(nullptr), left(nullptr), right(nullptr) {}
};
 
template<typename KEY, typename VALUE>
class map
{
private:
    Node<KEY, VALUE>* root;
public:
        map() : root(nullptr) {}
    ~map() { destroy(root); }
 
    map(const map<KEY, VALUE>& other)
    {
        if (other.root == nullptr)
            root = nullptr;
        else
            copyTree(root, other.root);
    }
 
    const map<KEY, VALUE>& operator=(const map<KEY, VALUE>& other)
    {
        if (this != &other)
        {
            if (root != nullptr)
                destroy(root);
            if (other.root == nullptr)
                root = NULL;
            else
                copyTree(root, other.root);
        }
        return *this;
    }
 
    void copyTree (Node<KEY, VALUE>*& copiedTreeRoot, Node<KEY, VALUE>* otherTreeRoot)
    {
        if (otherTreeRoot == nullptr)
            copiedTreeRoot = nullptr;
        else {
            copiedTreeRoot = new Node<KEY, VALUE>;
            copiedTreeRoot->id = otherTreeRoot->id;
            copiedTreeRoot->object = otherTreeRoot->object;
            copiedTreeRoot->color = otherTreeRoot->color;
            copiedTreeRoot->parent = otherTreeRoot->parent;
            copyTree(copiedTreeRoot->left, otherTreeRoot->left);
            copyTree(copiedTreeRoot->right, otherTreeRoot->right);
            //copyTree(copiedTreeRoot->parent, otherTreeRoot->parent);
        }
    }
};

Answer 1

Since you already have a working copy constructor and destructor, you can utilize copy / swap idiom:

#include <algorithm>
//...
const map<KEY, VALUE>& operator=(const map<KEY, VALUE>& other)
{
     if (this != &other)
     {
        map<KEY, VALUE> temp(other);
        std::swap(temp.root, root);
     }
     return *this;
}

This works due to simply creating a temporary map copied from other, and simply swapping out the current contents.

The flaw with your original code is that you destroyed the root, but you have no idea if the new in copytree will not throw. If that happens, you've corrupted your map.

Using copy/swap, a temporary is created -- if anything throws from creating the temporary, then your original map won't get corrupted.

Answer 2

You might pass new parent to CopyTree:

const map<KEY, VALUE>& operator=(const map<KEY, VALUE>& other)
{
    if (this != &other)
    {
        if (root != nullptr)
            destroy(root);
        copyTree(root, nullptr, other.root);
    }
    return *this;
}

void copyTree (Node<KEY, VALUE>*& copiedTreeRoot,
               Node<KEY, VALUE>* newParent,
               Node<KEY, VALUE>* otherTreeRoot)
{
    if (otherTreeRoot == nullptr)
        copiedTreeRoot = nullptr;
    else {
        copiedTreeRoot = new Node<KEY, VALUE>;
        copiedTreeRoot->id = otherTreeRoot->id;
        copiedTreeRoot->object = otherTreeRoot->object;
        copiedTreeRoot->color = otherTreeRoot->color;
        copiedTreeRoot->parent = newParent;

        copyTree(copiedTreeRoot->left, copiedTreeRoot, otherTreeRoot->left);
        copyTree(copiedTreeRoot->right, copiedTreeRoot, otherTreeRoot->right);
    }
}