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);
        }
    }
};

I'd start by adding a copy constructor to `Node` so you can move all that out of your `copyTree` function. If `other.root == nullptr` and you've done `destroy(root)` before it, I guess `root` still points at a now destroyed `Node`? So, what does your `destroy` function look like? Please make a [mcve]. — Ted Lyngmo, Dec 08 '20 at 21:51
I'd recommend to not call your class `map`, because it may be confused with `std::map`. Particularly, if you have to include a header containing a `using namespace std` you'll have a problem. — bjhend, Dec 08 '20 at 22:11
@TedLyngmo ok, here: https://github.com/insania37/binatyTree — yaromchikV, Dec 08 '20 at 22:25
@insania37 Put a [mcve] in the question instead of linking to it. — Ted Lyngmo, Dec 08 '20 at 22:48
@insania37 Temporary solutions always last longer than expected, even when considering this. — bjhend, Dec 08 '20 at 22:54
@bjhend: Eiffel tower was temporary... And still there in Paris. — Jarod42, Dec 08 '20 at 23:13
@insania37 -- Check the answer showing you how to simply create the assignment operator using `std::swap`. — PaulMcKenzie, Dec 09 '20 at 00:15

score 2 · Accepted Answer · answered Dec 08 '20 at 22:25

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);
    }
}

score 1 · Answer 2 · answered Dec 09 '20 at 00:10

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.

The copy constructor isn't working for the same reason as the assignation: OP has issue to assign parents with `CopyTree`. — Jarod42, Dec 09 '20 at 12:24
Yes, this works, but the `CopyTree` is still required for the copy constructor. The problem was with him. — yaromchikV, Dec 09 '20 at 18:29

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

2 Answers2