如何在 red-black 树中重载 operator=？ C++

Question

我有一个 red-black 树需要用赋值运算符重载。我有点让一棵二叉树的 operator= 超载了，它的节点不知道它们的 parents。但是，对于节点与左、右和 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

您可以将新父级传递给 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);
    }
}

Answer 2

因为你已经有了一个有效的复制构造函数和析构函数，你可以利用 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;
}

之所以有效，是因为简单地创建了一个从 other 复制的临时 map，并简单地换出当前内容。

您原始代码的缺陷在于您破坏了根目录，但您不知道 copytree 中的 new 是否不会 throw。如果发生这种情况，则说明您的地图已损坏。

使用 copy/swap，创建一个临时文件——如果创建临时文件有任何问题，那么您的原始文件 map 不会被破坏。

如何在 red-black 树中重载 operator=？ C++

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

c++

assignment-operator

red-black-tree