【C++】：红黑树
朋友们、伙计们，我们又见面了，本期来给大家解读一下有关多态的知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！
C 语 言 专 栏：C语言：从入门到精通
数据结构专栏：数据结构
个 人 主 页 ：stackY、
C + + 专 栏 ：C++
Linux 专 栏 ：Linux
目录
1. 红黑树的概念
2. 红黑树的性质
3. 红黑树节点的定义
4. 红黑树的插入
4.1 按照二叉搜索的树规则插入新节点
4.2 检测新节点插入后，红黑树的性质是否造到破坏
情况一：uncle节点存在且为红
情况二： uncle节点不存在或者存在且为黑
1. p为g的左，且cur为p的左或者p为g的右，且cur为p的右
2. p为g的左，且cur为p的右或者p为g的右，且cur为p的左
5. 红黑树的验证
6. 红黑树的其他接口
7. 红黑树与AVL树的比较
8. 完整代码
1. 红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
2. 红黑树的性质
- 1. 每个结点不是红色就是黑色
- 2. 根节点是黑色的
- 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
- 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
3. 红黑树节点的定义
红黑树节点的定义我们使用pair进行数据的存储，那么这里就存在一个问题，构造出来的节点默认是什么颜色呢？
根据红黑树的性质，每一条路径中黑色节点的数量必须相等，如果构造出来的节点默认设置为黑，那么在一条路径中插入一个黑色节点，为了维持红黑树的规则就需要在别的路径中也加上黑色节点，这样子做的话代价比较大，所以我们将构造出来的节点的颜色默认置为红色，这样子插入一个红色的节点对其他的路径并没有什么影响。
//红黑树节点的定义 template<class K, class V> struct RBTreeNode {RBTreeNode<K, T>* _left; //左子树节点RBTreeNode<K, T>* _right; //右子树节点RBTreeNode<K, T>* _parent; //父节点Color _col; //节点颜色pair<K, V> _kv; //节点的数据//节点的构造RBTreeNode(const pair<K, T>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){} };
4. 红黑树的插入
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
4.1 按照二叉搜索的树规则插入新节点
//插入bool Insert(const pair<K, V>& kv){//为空可以直接插入，并将根节点置为黑色if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;//不为空找到合适的插入位置while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}elsereturn false;}//链接//新插入的节点默认为红色节点cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//...return true;}
4.2 检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：如果其父亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的父亲节点颜色为红色时，就违反了不能有连在一起的红色节点，此时需要对红黑树分情况处理：首先我们要了解一下红黑树的基本情况：
cur(c)：代表当前节点
parent(p)：代表cur的父亲节点
uncle(u)：代表cur的叔叔节点
grandfather(g)：代表当前节点的祖父节点
情况一：uncle节点存在且为红
注意：这里显示的红黑树有可能是一棵完整的红黑树，也有可能是一棵子树。
这里有三个节点是已知情况，因为插入的默认节点颜色是红色，插入红色时是需要进行调整的，所以cur和parent是红色，那么grandfather节点必定是黑色。
如果叔叔节点存在且为红色，那么只需要进行简单的变色即可，将parent和uncle变为黑色，这时这个子树的每一个路径下的黑色节点就多了一个，因此还需要将grandfather节点变为红色，这样就使它的每一个路径少了一个黑色节点，这样才能平衡多出的黑色节点。
改变完颜色之后，由于我们不确定grandfather节点是否还有父亲节点，如果它的父亲节点为黑色，那么则不需要处理，如果它的父亲为红色节点，那么还需要继续向上处理，为了方便，我们可以将grandfather继续当作cur，继续向上调整。
综上所述：当uncle节点存在且为红色节点时，将parent和uncle改为黑色，然后将grandfather改为红色，再将grandfather继续当作新的cur，继续向上调整。
如果这里已经是一棵完整的红黑树了，此时的cur就变成了根节点，但是它被改成了红色，所以就需要再将根节点置为黑色。
代码实现：
//插入bool Insert(const pair<K, V>& kv){//和搜索二叉插入同样的逻辑//...//判断节点的颜色，是否破坏了平衡while (parent && parent->_col == RED){//祖父节点Node* grandfather = parent->_parent;//判断父亲与叔叔的位置if (parent == grandfather->_left){Node* uncle = grandfather->_right;//叔叔节点存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//将grandfather变为新的cur继续向上处理cur = grandfather;parent = cur->_parent;}//其他情况//...}else{Node* uncle = grandfather->_left;//叔叔节点存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//将grandfather变为新的cur继续向上处理cur = grandfather;parent = cur->_parent;}//其他情况//...}}//将根节点再次置黑保持红黑树的平衡_root->_col = BLACK;}
情况二： uncle节点不存在或者存在且为黑
这里还需要分了两种情况：
1. p为g的左，且cur为p的左或者p为g的右，且cur为p的右
这种情况如果只通过单纯的变色是不能达到效果的，需要配合旋转才能达到红黑树的平衡。
①如果parent为grandfather的左，且cur为parent的左
这种情况需要先以p为根节点进行右单旋，然后进行变色，需要将parent和grandfather变色，将parent变为黑色，将grandfather变为红色。
②如果parent为grandfather的右，且cur为parent的右
这种情况需要先以p为根节点进行左单旋，然后进行变色，需要将parent和grandfather变色，将parent变为黑色，将grandfather变为红色。
2. p为g的左，且cur为p的右或者p为g的右，且cur为p的左
这种情况类似于AVL树中的双旋，通过单旋+变色是不能达到红黑树的平衡的，需要经过两次旋转，再加变色才可以达到红黑树的平衡。
①如果parent为grandfather的左，且cur为parent的右
先以parent为根进行左旋，然后再以grandfather为根进行右旋，然后将cur变黑，将grandfater变红。
②如果parent为grandfather的右，且cur为parent的左
先以parent为根进行右旋，然后再以grandfather为根进行左旋，然后将cur变黑，将grandfather变红。
如果我们仔细观察，不难发现，在上述的两者双旋情况中，在旋转一次之后得到的红黑树和和1中的情况是一样的，那么也就说明了不一定cur是新插入的节点，还有可能是下面的子树在调整完之后将cur变为了红节点，然后导致红黑树的不平衡。
代码演示：
左单旋和右单旋就不做过多解释了，AVL树部分有详细的介绍。
//插入bool Insert(const pair<K, V>& kv){//为空可以直接插入，并将根节点置为黑色if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;//不为空找到合适的插入位置while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}elsereturn false;}//链接//新插入的节点默认为红色节点cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//判断节点的颜色，是否破坏了平衡while (parent && parent->_col == RED){//祖父节点Node* grandfather = parent->_parent;//判断父亲与叔叔的位置if (parent == grandfather->_left){Node* uncle = grandfather->_right;//叔叔节点存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//将grandfather变为新的cur继续向上处理cur = grandfather;parent = cur->_parent;}else //叔叔节点不存在或者存在且为黑{if (cur == parent->_left) //该路径的parent已经是grandfather的左{//旋转+变色Rotate_right(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //cur是parent的右{//双旋+变色Rotate_left(parent);Rotate_right(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else //parent == grandfather->_right{Node* uncle = grandfather->_left;//叔叔节点存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//将grandfather变为新的cur继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right) //该路径的parent已经是grandfather的右{//旋转+变色Rotate_left(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //cur是parent的左{Rotate_right(parent);Rotate_left(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//将根节点再次置黑保持红黑树的平衡_root->_col = BLACK;return true;}
5. 红黑树的验证
红黑树的检测分为两步：
- 1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
- 2. 检测其是否满足红黑树的性质
中序遍历比较简单，就不做赘述了，主要来看一下第二条：
首先红黑树的性质：
- 1. 每个结点不是红色就是黑色
- 2. 根节点是黑色的
- 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
①因为我们对颜色使用的是枚举，所以每个节点不是红色就是黑色。
②根节点是否为黑色只需要对_root的_col判断是否为黑色即可。
③判断是否存在连续的红色节点可以通过判断一个节点的父亲节点是否为红色即可。
④判断每条路径是否具有相同的黑色节点可以封装一个函数，然后传递一个路径中黑色节点的个数作为基准值，通过判断剩余路径黑色节点的个数与这个基准值相不相等即可。求每条路径的个数可以采用深度优先遍历找到黑色节点计数器++即可。
代码演示：
//判断是否平衡bool IsBalance(){if (_root == nullptr)return true;//1.判断根是否为黑if (_root->_col == RED)return false;int standard_val = 0; //最左路径的黑色节点个数Node* cur = _root;while (cur){if (cur->_col == BLACK)standard_val++;cur = cur->_left;}int Black_size = 0;return Check(_root,standard_val,Black_size);} private://判断是否平衡bool Check(Node* root, const int standard_val, int Black_size){if (root == nullptr){if (Black_size != standard_val) //比较黑色节点的个数{cout << "存在黑色节点数量不相等的路径" << endl;return false;}elsereturn true;}//判断它与它父亲的颜色if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}//黑色节点计数器++if (root->_col == BLACK){Black_size++;}//递归它的左右子树return Check(root->_left, standard_val, Black_size)&& Check(root->_right, standard_val, Black_size);}
6. 红黑树的其他接口
红黑树的查找、节点个数、树的高度
//高度int Height(){return _Height(_root);}//节点个数size_t Size(){return _Size(_root);}//查找Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;} private:size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}
7. 红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是
，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
8. 完整代码
#pragma once//枚举定义节点颜色 enum Color {RED, //红色BLACK //黑色 };//红黑树节点的定义 template<class K, class V> struct RBTreeNode {RBTreeNode<K, V>* _left; //左子树节点RBTreeNode<K, V>* _right; //右子树节点RBTreeNode<K, V>* _parent; //父节点Color _col; //节点颜色pair<K, V> _kv; //节点的数据//节点的构造RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){} };//红黑树的实现 template<class K, class V> class RBTree { public:typedef RBTreeNode<K, V> Node;//插入bool Insert(const pair<K, V>& kv){//为空可以直接插入，并将根节点置为黑色if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;//不为空找到合适的插入位置while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}elsereturn false;}//链接//新插入的节点默认为红色节点cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//判断节点的颜色，是否破坏了平衡while (parent && parent->_col == RED){//祖父节点Node* grandfather = parent->_parent;//判断父亲与叔叔的位置if (parent == grandfather->_left){Node* uncle = grandfather->_right;//叔叔节点存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//将grandfather变为新的cur继续向上处理cur = grandfather;parent = cur->_parent;}else //叔叔节点不存在或者存在且为黑{if (cur == parent->_left) //该路径的parent已经是grandfather的左{//旋转+变色Rotate_right(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //cur是parent的右{//双旋+变色Rotate_left(parent);Rotate_right(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else //parent == grandfather->_right{Node* uncle = grandfather->_left;//叔叔节点存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//将grandfather变为新的cur继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right) //该路径的parent已经是grandfather的右{//旋转+变色Rotate_left(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //cur是parent的左{Rotate_right(parent);Rotate_left(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//将根节点再次置黑保持红黑树的平衡_root->_col = BLACK;return true;}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}//判断是否平衡bool IsBalance(){if (_root == nullptr)return true;//1.判断根是否为黑if (_root->_col == RED)return false;int standard_val = 0; //最左路径的黑色节点个数Node* cur = _root;while (cur){if (cur->_col == BLACK)standard_val++;cur = cur->_left;}int Black_size = 0;return Check(_root,standard_val,Black_size);}//高度int Height(){return _Height(_root);}//节点个数size_t Size(){return _Size(_root);}//查找Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;} private:size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}//判断是否平衡bool Check(Node* root, const int standard_val, int Black_size){if (root == nullptr){if (Black_size != standard_val) //比较黑色节点的个数{cout << "存在黑色节点数量不相等的路径" << endl;return false;}elsereturn true;}//判断它与它父亲的颜色if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}//黑色节点计数器++if (root->_col == BLACK){Black_size++;}//递归它的左右子树return Check(root->_left, standard_val, Black_size)&& Check(root->_right, standard_val, Black_size);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}//右单旋void Rotate_right(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if(subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;subL->_parent = ppNode;}else{ppNode->_right = subL;subL->_parent = ppNode;}}}//左单旋void Rotate_left(Node* parent){Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;parent->_right = subRL;if (subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}} private:Node* _root = nullptr; };
朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，欲知后事如何，请听下回分解~，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！