🎇C++学习历程：入门

---

• 博客主页：一起去看日落吗
• 持续分享博主的C++学习历程
• 博主的能力有限，出现错误希望大家不吝赐教
• 分享给大家一句我很喜欢的话： 也许你现在做的事情，暂时看不到成果，但不要忘记，树🌿成长之前也要扎根，也要在漫长的时光🌞中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭🐾。

---

🍁 🍃 🍂 🌿

目录

• 🌿 1. 红黑树
• • 🍃 1.1 红黑树的概念
  • 🍃 1.2 红黑树的性质
  • 🍃 1.3 红黑树节点的定义
  • 🍃 1.4 红黑树结构
  • 🍃 1.5 红黑树的插入操作
  • 🍃 1.6 红黑树的验证
  • 🍃 1.7 红黑树与AVL树的比较
  • 🍃 1.8 红黑树的模拟实现
• 🌿 2. 红黑树模拟实现STL中的map与set
• • 🍃 2.1 改造红黑树
  • 🍃 2.2 map的模拟实现
  • 🍃 2.3 set的模拟实现
  • 🍃 2.4 测试

🌿 1. 红黑树

🍃 1.1 红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。

🍃 1.2 红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点
个数的两倍？

答：假设黑色节点数量有N个，最短路径为：logN,最长路径为：2*logN,因此最长路径中节点个数不会超过最短路径中节点个数的两倍，所以如果用红黑树来完成查找效率也是非常高的。

🍃 1.3 红黑树节点的定义

//节点不是黑就是红，因此可以直接用枚举
enum Colour
{RED,BLACK
};//节点的颜色
template
struct RBTreeNode
{RBTreeNode* _left;//节点左孩子RBTreeNode* _right;//节点右孩子RBTreeNode* _parent;//节点的父亲pair _kv;//节点中存放的键值对Colour _col;//节点的颜色RBTreeNode(const pair kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};

思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？

答：在上面的性质中第三条和第四条是最重要的两点性质。假设我们默认颜色给黑色，那么必然会破环性质4(每条路径上包含相同数目的黑节点),如果破坏性质4代价会非常大，这是一种全局的破坏，其他每条路径的节点会因该路径增加了一个黑节点而不满足红黑树性质，调整起来非常麻烦；那么如果我们默认颜色给红色呢，必然会破坏性质3(没有连续的红节点)，但是破坏这条性质只会影响当前路径，并不会对其他路径造成影响，影响面小。所以综上所述我们不难发现，默认给成红色是更好的。

🍃 1.4 红黑树结构

在STL中，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：

注意： 在下面的实现中，我们采用不带头节点的方式来模拟实现红黑树

🍃 1.5 红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索树规则插入新节点

2. 检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其父节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的父节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

在分情况讨论之前记住一句话：关键看叔叔的脸色！

• 情况一： cur为红，p为红，g为黑，u存在且为红

• 情况二: cur为红，p为红，g为黑，u不存在/u为黑

• 情况三: cur为红，p为红，g为黑，u不存在/u为黑

• 总结
  

pair Insert(const pair kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根节点给黑色return make_pair(_root, true);}Node* cur = _root;Node* parent = nullptr;while (cur)//循环去找空位{if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if(kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return make_pair(cur, false);}}Node* newnode = new Node(kv);newnode->_col = RED;//链接上新节点if (kv.first > parent->_kv.first){parent->_right = newnode;newnode->_parent = parent;}else{parent->_left = newnode;newnode->_parent = parent;}cur = newnode;//父节点存在且父节点为红色时需要继续处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//关键看叔叔的脸色if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//具体变色的情况需要画图分析:grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//注意需要继续向上处理,容易忘记cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){RotateR(grandfather);//右单旋parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);//先以父节点为旋转点左旋RotateR(grandfather);//再以g为旋转点右旋cur->_col = BLACK;grandfather->_col = RED;}break;//旋转+变色过后一定是满足所有性质的直接退出循环}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else // 情况2：+ 情况3：{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // cur == parent->_left{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(newnode, true);}

🍃 1.6 红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质

bool _CheckBlance(Node* root, int blackNum, int count)//balckNum相当于一个标尺，count就是用来记录每条路径的黑节点数目{if (root == nullptr)//如果root走到空节点{if (count != blackNum)//count不等于最左路径的黑色节点数{cout << "黑色节点的数量不相等" << endl;return false;//返回假}return true;//否则返回真}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){count++;}return _CheckBlance(root->_left, blackNum, count)&& _CheckBlance(root->_right, blackNum, count);//再递归到各子树的子问题}bool CheckBlance(){if (_root == nullptr){return true;}if (_root->_col == RED){cout << "根节点是红色的" << endl;return false;}// 找最左路径做黑色节点数量参考值int blackNum = 0;Node* left = _root;while (left){if (left->_col == BLACK){blackNum++;}left = left->_left;}int count = 0;return _CheckBlance(_root, blackNum, count);}

🍃 1.7 红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log2Nlog_2 Nlog2​N)，红黑树不追
求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，
所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红
黑树更多。

🍃 1.8 红黑树的模拟实现

RBTree.h

//
//  RBTree.hpp
//  RedBlackTree
//
//  Created by 卜绎皓 on 2022/11/17.
//#pragma once
#include
using namespace std;enum Colour
{RED,BLACK
};//节点的颜色
template
struct RBTreeNode
{RBTreeNode* _left;//节点左孩子RBTreeNode* _right;//节点右孩子RBTreeNode* _parent;//节点的父亲pair _kv;//节点中存放的T类型的数据Colour _col;//节点的颜色RBTreeNode(const pair kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};template
class RBTree
{typedef RBTreeNode Node;
public:RBTree():_root(nullptr){}//拷贝构造和赋值拷贝也需要自行实现这里不做赘述~RBTree(){Destory(_root);_root = nullptr;}void Destory(Node* root){if (root == nullptr){return;}//利用后序遍历释放节点Destory(root->_left);Destory(root->_right);delete root;}void RotateR(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR != nullptr)//注意:这里一定要判断不为空的，因为下面可能会出现空指针的解引用{subLR->_parent = parent;}subL->_right = parent;Node* parentParent = parent->_parent;//一定要在改变链接关系之前把这个指针存下来parent->_parent = subL;//if (parentParent == nullptr)或者采用这个条件也是可以的if (parent == _root){_root = subL;_root->_parent = nullptr;}else{//这里注意:parent还有父母时，链接之前需要注意判断到底是右孩子还是左孩子if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;//最后还要把父指针关系链接上}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//先把subR的左孩子赋值给parent的右节点parent->_right = subRL;if (subRL != nullptr)//注意一定要判断是否为空的情况{subRL->_parent = parent;//然后链接parent指针}//然后subR的左节点链接上parentsubR->_left = parent;Node* parentParent = parent->_parent;//提前记录parent->_parent = subR;//if (parentParent == nullptr)if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subR;elseparentParent->_right = subR;subR->_parent = parentParent;}}pair Insert(const pair kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根节点给黑色return make_pair(_root, true);}Node* cur = _root;Node* parent = nullptr;while (cur)//循环去找空位{if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if(kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return make_pair(cur, false);}}Node* newnode = new Node(kv);newnode->_col = RED;//链接上新节点if (kv.first > parent->_kv.first){parent->_right = newnode;newnode->_parent = parent;}else{parent->_left = newnode;newnode->_parent = parent;}cur = newnode;//父节点存在且父节点为红色时需要继续处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//关键看叔叔的脸色if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//具体变色的情况需要画图分析:grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//注意需要继续向上处理,容易忘记cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){RotateR(grandfather);//右单旋parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);//先以父节点为旋转点左旋RotateR(grandfather);//再以g为旋转点右旋cur->_col = BLACK;grandfather->_col = RED;}break;//旋转+变色过后一定是满足所有性质的直接退出循环}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else // 情况2：+ 情况3：{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // cur == parent->_left{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(newnode, true);}void _InOrder(Node* root)//中序遍历递归打印{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":"<_kv.second<_right);}void InOrder(){_InOrder(_root);cout << endl;}bool _CheckBlance(Node* root, int blackNum, int count)//balckNum相当于一个标尺，count就是用来记录每条路径的黑节点数目{if (root == nullptr)//如果root走到空节点{if (count != blackNum)//count不等于最左路径的黑色节点数{cout << "黑色节点的数量不相等" << endl;return false;//返回假}return true;//否则返回真}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){count++;}return _CheckBlance(root->_left, blackNum, count)&& _CheckBlance(root->_right, blackNum, count);//再递归到各子树的子问题}bool CheckBlance(){if (_root == nullptr){return true;}if (_root->_col == RED){cout << "根节点是红色的" << endl;return false;}// 找最左路径做黑色节点数量参考值int blackNum = 0;Node* left = _root;while (left){if (left->_col == BLACK){blackNum++;}left = left->_left;}int count = 0;return _CheckBlance(_root, blackNum, count);}
private:Node* _root;
};

🌿 2. 红黑树模拟实现STL中的map与set

对map和set进行封装，虽然要传不同的参数类型，但是我们只需传个模版，根据不同的需要取不同的参数类型

🍃 2.1 改造红黑树

	因为关联式容器中存储的是的键值对，因此k为key的类型，ValueType: 如果是map，则为pair; 如果是set，则为kKeyOfValue: 通过value来获取key的一个仿函数类

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明

#pragma once
#include
using namespace std;enum Colour
{RED,BLACK
};//节点的颜色
template
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};
template
struct __TreeIterator//封装迭代器
{typedef RBTreeNode Node;//迭代器就是节点的指针typedef __TreeIterator Self;Node* _node;//__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator != (const Self& s) const{return _node != s._node;}bool operator == (const Self& s) const{return _node == s._node;}// 迭代器的难点Self& operator++(){//++注意画图分析if (_node->_right)//节点的右子树不为空{// 下一个访问就是右树中，中序的第一个节点Node* left = _node->_right;while (left->_left)//循环去找最左节点{left = left->_left;}_node = left;}else{// 找祖先里面不是父亲的右的那个节点// 因为 cur 右为空，说明cur所在的子树已经访问完了// cur是parent的右的，说明parent包括其所在子树都访问完了，循环往上去找Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right)//如果父亲不为空或者cur为父亲的右节点{cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){// 下一个需要访问左子树的最右节点Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else{Node* cur = _node;Node* parent = cur->_parent;//如果父节点存在且cur一直为父节点的左节点循环继续向上找while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};
template//多添加一个模板参数用以map和set进行封装
class RBTree
{typedef RBTreeNode Node;
public:typedef __TreeIterator < T, T&, T* > iterator;typedef __TreeIterator < T, const T&, const T* > const_iterator;iterator begin(){Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}RBTree():_root(nullptr){}void Destory(Node* root){if (root == nullptr){return;}Destory(root->_left);Destory(root->_right);delete root;}~RBTree(){Destory(_root);_root = nullptr;}Node* Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) > key){cur = cur->_left;}else if (kot(cur->_data) < key){cur = cur->_right;}else{return cur;}}return nullptr;}pair Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}KeyOfT kot;//仿函数对象,重载operator()即可Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}Node* newnode = new Node(data);newnode->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = newnode;newnode->_parent = parent;}else{parent->_left = newnode;newnode->_parent = parent;}cur = newnode;// 如果父亲存在，且颜色为红色就需要处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;// 关键是看叔叔if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况1：uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 情况2+3：uncle不存在 uncle存在且为黑{// 情况2：单旋if (cur == parent->_left){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else // 情况3：双旋{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // parent == grandfather->_right{Node* uncle = grandfather->_left;// 情况1：if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else // 情况2：+ 情况3：{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // cur == parent->_left{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 插入结束break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}void 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 (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* parentParent = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;}}bool _CheckBlance(Node* root, int blackNum, int count){if (root == nullptr){if (count != blackNum){cout << "黑色节点的数量不相等" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){count++;}return _CheckBlance(root->_left, blackNum, count)&& _CheckBlance(root->_right, blackNum, count);}bool CheckBlance(){if (_root == nullptr){return true;}if (_root->_col == RED){cout << "根节点是红色的" << endl;return false;}// 找最左路径做黑色节点数量参考值int blackNum = 0;Node* left = _root;while (left){if (left->_col == BLACK){blackNum++;}left = left->_left;}int count = 0;return _CheckBlance(_root, blackNum, count);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":"<_kv.second<_right);}void InOrder(){_InOrder(_root);cout << endl;}
private:Node* _root;
};

🍃 2.2 map的模拟实现

#pragma once
#include"RBTree.h"namespace Bernard
{templateclass map{struct MapKeyOfT//定义map的仿函数内部类{//map的V类型为pair键值对const K& operator()(const pair& kv){return kv.first;//返回pair中的第一个值}};public:typedef typename RBTree, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair insert(const pair& kv){return _t.Insert(kv);}V& operator[](const K& key){pair ret = insert(make_pair(key, V()));return ret.first->second;}private:RBTree, MapKeyOfT> _t;};
}

🍃 2.3 set的模拟实现

#pragma once
#include"RBTree.h"namespace Bernard
{templateclass set{//set里面定义内部类重载operator()//set的V类型为Kstruct SetKeyOfT{const K& operator()(const K& key){return key;//直接返回key}};public:typedef typename RBTree::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair insert(const K& k){return _t.Insert(k);}private:RBTree _t;};
}

🍃 2.4 测试

//
//  main.cpp
//  封装map和set
//
//  Created by 卜绎皓 on 2022/11/17.
//#include "RedBlackTree.hpp"
#include "my_map.hpp"
#include "my_set.hpp"int main()
{Bernard::map m;m.insert(make_pair(1, 1));m.insert(make_pair(3, 3));m.insert(make_pair(0, 0));m.insert(make_pair(9, 9));Bernard::map::iterator it = m.begin();while (it != m.end()){cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;++it;}Bernard::set s;s.insert(1);s.insert(5);s.insert(2);s.insert(1);s.insert(13);s.insert(0);s.insert(15);s.insert(18);Bernard::set::iterator sit = s.begin();while (sit != s.end()){cout << *sit << " ";++sit;}cout << endl;return 0;
}