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