深入剖析：基于红黑树实现自定义 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() {// 测试setzdf::set<int> s;s.insert(3);s.insert(1);s.insert(2);// 测试mapzdf::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】