c++assignment-operatorred-black-tree

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


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

Solution

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