深入剖析：基于红黑树实现自定义 map 和 set 容器

🌟 快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。🌟 

        在 C++ 标准模板库（STL）的大家庭里，map和set可是超级重要的关联容器成员呢😎！它们凭借红黑树这一强大的数据结构，实现了查找、插入和删除等操作的高效运行。

        现在，就让我们一步步深入探索如何亲手基于红黑树打造自定义的map和set容器吧🧐！

目录

深入剖析：基于红黑树实现自定义 map 和 set 容器 🚀 

一、红黑树基础结构与操作 🌳

1. 红黑树节点结构 📄

2. 红黑树类基本框架 📐

3. 左旋操作 🔄

4. 右旋操作 🔄

5. 插入修复 🔧

6. 插入操作 📥

7. 查找操作 🔍

8. 红黑树析构函数 🗑️

二、自定义 map 和 set 实现 🛠️

1. 自定义 set 实现 📚

（1）SetKeyOfT 仿函数 📐

2. 自定义 map 实现 🗺️

（1）MapKeyOfT 仿函数 📐

三、测试代码 🧪

一、红黑树基础结构与操作 🌳

1. 红黑树节点结构 📄

红黑树的节点结构包含节点颜色、父节点指针、左右子节点指针以及存储的数据。

• 实现思路：定义一个结构体来表示红黑树的节点，包含节点颜色、父节点指针、左右子节点指针和存储的数据。为方便后续操作，节点默认颜色设为红色，新插入节点通常为红色，有助于维持红黑树性质。
• 代码实现：

// 定义红黑树节点颜色
enum Colour {
    RED,
    BLACK
};

// 红黑树节点结构体
template<class T>
class RBTreeNode {
public:
    RBTreeNode(const T& data) : _data(data),
        _left(nullptr),
        _right(nullptr),
        _parent(nullptr),
        _col(RED)
    {}

    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    Colour _col;

    T _data;
};

2. 红黑树类基本框架 📐

• 实现思路：定义红黑树类，包含根节点指针。提供插入、查找等基本操作函数声明，用于数据的插入、检索；同时定义左旋、右旋等内部操作函数声明，用于调整树结构，维持红黑树性质。
• 代码实现：

template<class K, class T, class KeyOfT>
class RBTree {
public:
    typedef RBTreeNode<T> Node;
    typedef _TreeIterator<T, T&, T*> iterator;
    typedef _TreeIterator<T, const T&, const T*> const_iterator;

    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;
    pair<Node*, bool> insert(const T& data);

private:
    Node* _root = nullptr;
    void RotateL(Node* parent);
    void RotateR(Node* parent);
    void RotateRL(Node* parent);
    void RotateLR(Node* parent);
};

3. 左旋操作 🔄

实现步骤👇

• 保存关键节点指针：

  • 保存 parent 的右子节点 subR 和 subR 的左子节点 subRL。

• 调整 parent 的右子节点：

  • 将 parent 的右子节点更新为 subRL。
  • 如果 subRL 不为空，将 subRL 的父节点指针指向 parent。

• 调整 subR 的左子节点：

  • 将 subR 的左子节点更新为 parent。
  • 保存 parent 的父节点 parentParent。
  • 将 parent 的父节点指针指向 subR。

• 更新根节点或父节点的子节点指针：

  • 如果 parent 是根节点（即 parentParent 为空），将 subR 设为新的根节点，并将 subR 的父节点指针置为空。
  • 否则，根据 parent 是 parentParent 的左子节点还是右子节点，更新 parentParent 的相应子节点指针为 subR，并将 subR 的父节点指针指向 parentParent。

代码实现： 

template<class K, class T, class KeyOfT>
void RBTree<K, T, KeyOfT>::RotateL(Node* parent) { 
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    parent->_right = subRL;
    if (subRL) {
        subRL->_parent = parent;
    }

    subR->_left = parent;
    Node* parentParent = parent->_parent;
    parent->_parent = subR;

    if (parentParent == nullptr) {
        _root = subR;
        subR->_parent = nullptr;
    }
    else {
        if (parentParent->_left == parent) {
            parentParent->_left = subR;
        }
        else {
            parentParent->_right = subR;
        }
        subR->_parent = parentParent;
    }
}

4. 右旋操作 🔄

• 实现思路：右旋操作以 parent 为中心，交换其与左子节点 subL 位置，调整 subLR 指针，更新根或父节点指向维持平衡
• 代码实现：

template<class K, class T, class KeyOfT>
void RBTree<K, T, KeyOfT>::RotateR(Node* parent) { 
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    parent->_left = subL->_right;
    if (subLR) {
        subLR->_parent = parent;
    }

    subL->_right = parent;
    Node* parentParent = parent->_parent;
    parent->_parent = subL;

    if (parentParent == nullptr) {
        _root = subL;
        subL->_parent = nullptr;
    }
    else {
        if (parentParent->_left == parent) {
            parentParent->_left = subL;
        }
        else {
            parentParent->_right = subL;
        }
        subL->_parent = parentParent;
    }
}

5. 插入修复 🔧

• 实现思路：插入新节点后，红黑树的性质可能会被破坏，需要进行修复操作。修复操作主要根据新节点的父节点和叔节点的颜色进行分类处理，通过旋转和颜色调整来恢复红黑树的性质。
• 代码实现：

pair<Node*,bool> insert(const T& data)
{
    if (_root == nullptr)
    {
        _root = new Node(data);
        _root->_col = BLACK;
        return make_pair(_root, true);
    }
    Node* cur = _root;
    Node* parent = nullptr;
    KeyOfT kot;

    while (cur)
    {
        parent = cur;
        if (kot(cur->_data) < kot(data))
        {
            cur = cur->_right;
        }
        else if (kot(cur->_data) > kot(data))
        {
            cur = cur->_left;
        }
        else
        {
            return make_pair(cur, false);
        }
    }

    //新增结点给红色
    cur = new Node(data);
    Node* newNode = cur;
    cur->_parent = parent;
    if (kot(parent->_data) < kot(cur->_data))
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }

    while (parent && parent->_col == RED)
    {
        //找叔叔
        Node* grandfather = parent->_parent;
        Node* uncle = nullptr;
        if (parent == grandfather->_left)
        {
            uncle = grandfather->_right;
        }
        else
        {
            uncle = grandfather->_left;
        }
        if (uncle && uncle->_col == RED)//满足规则一，父亲和叔叔变黑，爷爷变红
        {
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;

            //继续向上更新
            cur = grandfather;
            parent = grandfather->_parent;
        }
        else //叔叔 不存在 或  存在且为黑
        {
            if (parent == grandfather->_left && cur == parent->_left)//右单旋
            {
                RotateR(grandfather);
                //变色
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else if (parent == grandfather->_right && cur == parent->_right)//左单旋
            {
                RotateL(grandfather);
                //变色
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else if (parent == grandfather->_left && cur == parent->_right)//折射，双旋
            {
                RotateLR(grandfather);
                //变色
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
            else if (parent == grandfather->_right && cur == parent->_left)//折射，双旋
            {
                RotateRL(grandfather);
                //变色
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
        }
    }

    _root->_col = BLACK;

    return make_pair(newNode, true);
}

6. 插入操作 📥

• 实现思路：首先找到合适的插入位置，创建新节点并插入到树中，然后调用插入修复函数来恢复红黑树的性质。
• 代码实现：

template<class K, class T, class KeyOfT>
pair<typename RBTree<K, T, KeyOfT>::Node*, bool> RBTree<K, T, KeyOfT>::insert(const T& data) {
    if (_root == nullptr) {
        _root = new Node(data);
        _root->_col = BLACK;
        return make_pair(_root, true);
    }
    Node* cur = _root;
    Node* parent = nullptr;
    KeyOfT kot;

    while (cur) {
        parent = cur;
        if (kot(cur->_data) < kot(data)) {
            cur = cur->_right;
        }
        else if (kot(cur->_data) > kot(data)) {
            cur = cur->_left;
        }
        else {
            return make_pair(cur, false);
        }
    }

    // 插入新节点并设置颜色
    cur = new Node(data);
    Node* newNode = cur;
    cur->_parent = parent;
    if (kot(parent->_data) < kot(cur->_data)) {
        parent->_right = cur;
    }
    else {
        parent->_left = cur;
    }

    while (parent && parent->_col == RED) {
        // 情况分类
        Node* grandfather = parent->_parent;
        Node* uncle = nullptr;
        if (parent == grandfather->_left) {
            uncle = grandfather->_right;
        }
        else {
            uncle = grandfather->_left;
        }
        if (uncle && uncle->_col == RED) { // 叔叔节点存在且为红色
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;

            // 继续向上调整
            cur = grandfather;
            parent = grandfather->_parent;
        }
        else { // 叔叔节点不存在或为黑色
            if (parent == grandfather->_left && cur == parent->_left) { // 左左情况
                RotateR(grandfather);
                // 调整颜色
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else if (parent == grandfather->_right && cur == parent->_right) { // 右右情况
                RotateL(grandfather);
                // 调整颜色
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else if (parent == grandfather->_left && cur == parent->_right) { // 左右情况
                RotateLR(grandfather);
                // 调整颜色
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
            else if (parent == grandfather->_right && cur == parent->_left) { // 右左情况
                RotateRL(grandfather);
                // 调整颜色
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
        }
    }

    _root->_col = BLACK;

    return make_pair(newNode, true);
}

7. 查找操作 🔍

• 实现思路：从根节点开始，根据键的大小比较，递归地在左子树或右子树中查找目标节点。
• 代码实现：

template<class K, class T, class KeyOfT>
RBTreeNode<T>* RBTree<K, T, KeyOfT>::Find(const K& key) {
    RBTreeNode<T>* current = _root;
    KeyOfT kot;
    while (current) {
        if (key < kot(current->_data)) {
            current = current->_left;
        }
        else if (key > kot(current->_data)) {
            current = current->_right;
        }
        else {
            return current;
        }
    }
    return nullptr;
}

8. 红黑树析构函数 🗑️

• 实现思路：采用后序遍历的方式递归删除树中的所有节点，释放内存。
• 代码实现：

template<class K, class T, class KeyOfT>
RBTree<K, T, KeyOfT>::~RBTree() {
    auto destroyTree = [](RBTreeNode<T>* node) {
        if (node != nullptr) {
            destroyTree(node->left);
            destroyTree(node->right);
            delete node;
        }
    };
    destroyTree(_root);
}

二、自定义 map 和 set 实现 🛠️

1. 自定义 set 实现 📚

（1）SetKeyOfT 仿函数 📐

• 实现思路：由于set中存储的元素就是键，因此仿函数直接返回元素本身。
• 代码实现：

namespace zdf {
    template<class K>
    class set {
    public:
        struct SetKeyOfT {
            const K& operator()(const K& key) {
                return key;
            }
        };
        // 定义迭代器类型
        typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
        typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

        iterator begin() const {
            return _t.begin();
        }

        iterator end() const {
            return _t.end();
        }

        pair<iterator, bool> insert(const K& key) {
            return _t.insert(key);
        }

    private:
        RBTree<K, K, SetKeyOfT> _t;
    };
}

2. 自定义 map 实现 🗺️

（1）MapKeyOfT 仿函数 📐

• 实现思路：map中存储的是键值对，仿函数从键值对中提取键。
• 代码实现：

namespace zdf {
    template<class K, class V>
    class map {
        struct MapKeyOfT {
            const K& operator()(const std::pair<K, V>& kv) {
                return kv.first;
            }
        };
    public:
        typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT>::iterator iterator;
        typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;


        iterator begin() {
            return _t.begin();
        }

        iterator end() {
            return _t.end();
        }

        V& operator[](const K& key) {
            std::pair<iterator, bool> ret = insert(std::make_pair(key, V()));
            return ret.first->second;
        }

        pair<iterator, bool> insert(const std::pair<K, V>& kv) {
            return _t.insert(kv);
        }

    private:
        RBTree<K, std::pair<const K, V>, MapKeyOfT> _t;
    };
}

三、测试代码 🧪

#include <iostream>

int main() {
    // 测试set
    zdf::set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(2);

    // 测试map
    zdf::map<int, std::string> m;
    m.insert({ 1, "one" });
    m.insert({ 2, "two" });
    m[3] = "three";

    std::cout << "Map value at key 3: " << m[3] << std::endl;

    return 0;
}

        通过以上步骤，我们基于红黑树实现了自定义的map和set容器，每个函数的实现思路和代码都进行了详细讲解。这些实现展示了红黑树在关联容器中的重要应用，以及如何通过封装和扩展红黑树来实现高效的数据存储和操作。 🎉

欢迎关注我 👉【A charmer】