红黑树简述

红黑树的概念

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

红黑树的性质

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

🚀根据红黑树的性质，可以得到红黑树最长路径的长度不超过最短路径长度的2倍，所以红黑树不是高度平衡的，也就意味着它的查询效率一定不如AVL树，因为AVL树的高度平衡的。但是红黑树的查询效率也不低，假设有一颗N个结点的AVL树，那么树的高度就是logN。但如果有一颗N个结点的红黑树，假设黑色结点为N - i个（黑色结点的个数肯定是小于等于N的）那么红黑树一条最短的路径为log（N - i）接近于logN，红黑树最长的一条路径假设为最短路径的2倍，2log（N - i），接近于2logN。
假设N为10亿，对于AVL树来说查找30次即可，对于红黑树需要60次（实际中肯定是小于60的），可见它们查找的性能相近。

红黑树结点定义

🚀树的接结点的定义，采用三指针结构（左子树指针，右子树指针，parent指针），存储的内容还有结点的颜色和pair结构

typedef enum color
{BLACK,RED
}color;
template<class K, class V>
struct TreeNode
{
public:TreeNode<K, V>(const pair<K, V>& kv):_kv(kv), _col(RED){}
public:color _col;pair<K, V> _kv;TreeNode<K, V>* _left = nullptr;TreeNode<K, V>* _right = nullptr;TreeNode<K, V>* _parent = nullptr;
};

一，红黑树的插入

🚀 根据红黑树的规则，我们知道插入新的结点，最好插入红色的结点，因为黑色节点一定会导致违反每条路径上的黑色节点的数目相同的规则。
🚀 红黑树的插入主要分四种情况：
1，父节点为黑色。
2，父节节点为红色，叔叔结点存在且为红色。
2，父亲节点为红色，叔叔结点存在且为黑色。
4，父亲节点为红色，叔叔结点不存在。

插入调整

🚀情况1：父亲结点为黑色，那么不需要调整。
🚀情况2：父亲节点为红色，叔叔结点存在且为红色。

解决方法：
1，parent结点变黑，uncle结点变黑
2，grandfather结点变红，继续向上调整（由于grandfather变成了红色，ppnode结点如果为红色还需继续调整）

向上调整过程中可能一致调整到根节点，但是根节点必须是黑色，那么就相当于每条路径多了一个黑色结点。

注： p结点为pp结点的右子树时，调整方法类似，就不再叙述。

🚀情况3：（1）父亲结点为红色，叔叔结点存在且为黑色。且cur为父亲结点左子树。

解决方法：
1，parent结点颜色变黑，grandfather结点的颜色变红
2，以grandfather结点为根的子树右旋

🚀情况3：（2）父亲结点为红色，叔叔结点存在且为黑色。且cur为父亲结点右子树。

解决方法：
1，对parent为根节点的子树进行左旋，转化为（1）情况
2，此时cur结点变黑，grandfather结点变红
3，以grandfather结点为根的子树右旋

情况3中的两种情况，必然是通过情况2向上调整过程中形成的，因为如果不是向上调整过程中形成的话，那么cur原本的位置就是NULL，那么这条路径上的黑色结点不然比叔叔结点所在路径的黑色节点要少。

注： parent结点为grandfather结点的右子树情况与上述情况类似，就不再叙述。

🚀情况4：（1）父亲节点为红色，且没有叔叔结点。且cur结点为父亲的左子树

解决方法：
1，parent结点变黑，grandfather结点变红
2，以grandfather结点为根节点的子树右旋

🚀情况4：（2）父亲节点为红色，且没有叔叔结点。且cur结点为父亲的右子树

解决方法：
1，以parent为根节点的子树左旋
2，cur结点变黑，grandfather结点变红
3，以grandfather结点为根节点的子树右旋

注： parent结点为grandfather结点右子树的情况与上述情况类似，不再叙述。

插入代码

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->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{//已经存在了return false;}}//找到了属于它的位置,插入cur = new node(kv);cur->_parent = parent;if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}//只要parent结点存在，并且其结点为颜色为红色就需要调整while (parent && parent->_col == RED){node* grandfather = parent->_parent;if (parent == grandfather->_left){//1,第一种情况，存在叔叔结点，并且为红色if (grandfather->_right && grandfather->_right->_col == RED){//祖父结点变红，父亲结点和叔叔结点变黑，继续向上调整，直到根节点为止。grandfather->_col = RED;parent->_col = BLACK;grandfather->_right->_col = BLACK;cur = grandfather;parent = cur->_parent;}//2,叔叔结点不存在或者为黑色else{//2.1 cur为parent的左子树，那么只需要祖父为根的树右旋即可if (cur == parent->_left){grandfather->_col = RED;parent->_col = BLACK;RotateR(grandfather);}//2.2 cur为parent的右子树，那么先对parent左旋，在对祖父右旋else if (cur == parent->_right){grandfather->_col = RED;cur->_col = BLACK;RotateLR(grandfather);}break;}}else{if (grandfather->_left && grandfather->_left->_col == RED){grandfather->_col = RED;parent->_col = BLACK;grandfather->_left->_col = BLACK;cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){grandfather->_col = RED;parent->_col = BLACK;RotateL(grandfather);}else if (cur == parent->_left){grandfather->_col = RED;cur->_col = BLACK;RotateRL(grandfather);}break;}}}_root->_col = BLACK;return true;
}

二，红黑树的验证

🚀红黑树的验证就是验证红黑树的5条性质：显然1 ， 2， 5 是不需要验证的，只需要验证：每条路径上的黑色节点的数目一致，和没有连续的红色结点的性质即可。

bool IsBalance()
{if (_root == nullptr){return true;}if (_root->_col == RED){cout << "违反规则1，根节点的颜色为黑色" << endl;return false;}size_t blackCount = 0;node* cur = _root;while (cur){if (cur->_col == BLACK)blackCount++;cur = cur->_left;}return _IsBalance(_root, 0, blackCount);
}

bool _IsBalance(node* root, size_t k, size_t blackCount)
{if (root == nullptr){if (k != blackCount){cout << "违反规则4，每条路径具有相同的黑色节点" << endl;return false;}return true;}if (root->_col == BLACK){k++;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << "违反性质3，存在相邻的红色结点" << endl;return false;}return _IsBalance(root->_left, k, blackCount) &&_IsBalance(root->_right, k, blackCount);
}

🚀由于，函数的返回值必须是bool类型，但是我们还要计算每条路径上的黑色结点的个数，所以我们可以先计算出一条路径上黑色结点的个数blackcount，然后以参数的形式传给函数。

三，红黑树的删除

🚀红黑树删除结点的逻辑大体分三步：
1，找到要删除的结点
2，调整红黑树的平衡
3，删除结点

🚀红黑树的删除大体上分为两种情况：
1，删除的结点是叶子结点
2，删除的结点只有左子树或者只有右子树

注： 对于一颗二叉搜索树，当要删除的结点既有左子树又有右子树，通常是找一个替代结点（要删除结点的右子树中值最小的结点，或者左子树中值最大的结点），将要删除的结点的值改为替代结点的值，然后删除替代节点即可，这样就转化为上述的两种情况。

待删除的结点只有一个子树

🚀首先，我们先讨论删除的结点只有一个子树的情况。

删除结点颜色为红色

当删除的结点是红色结点的时候，其实只有一种情况：其左子树或者右子树为红色。

对于这种情况直接删除待删除的结点即可，不需要调整。

注： ：红黑树的规则之一是：每条路径的黑色结点的数目相同，如果待删除的结点的子树为黑色时，那么就会使得每条路径的黑色结点数目不一致。所以这种情况是不存在的，图示：

删除结点颜色为黑色

这种情况与删除结点为红色时相似，只有一种情况：删除结点的左子树或者右子树为红色。

对于这种情况，不需要调整，直接删除即可。

注： 待删除结点的左子树为黑色或者右子树为黑色的时候，这种场景是不存在的，违反了红黑树每条路径的黑色节点的数目一致的规则。图示：

下面，再谈删除的结点为叶子结点的情况。

删除的结点为叶子节点

删除结点颜色为红色

删除结点为叶子结点，并且其颜色是红色那么说明删除这个节点并不会影响红黑树的平衡，所以不用做后序调整，直接删除即可。

删除结点颜色为黑色

🚀删除结点颜色为黑色，这种情况是最复杂的，其还会分为四种小情况。
注意： 由于情况比较复杂，下面的讲述就是以删除结点为其父节点的左子树的情况，为父节点右子树的情况与此很类似，自行脑补。
1，brother结点为红色。

删除黑色结点必然会使此路径上黑色节点减一导致红黑树不再平衡，所以需要调整。调整的方式为：bro结点颜色变黑，parent结点颜色变红，parent结点左旋。之后就会变成后序的情况。

注： 情况1是如何变成情况2 3 4的：
(1).当bro结点的左子树存在（记作left）且为黑色并且left的左右子树都为黑色或者左右子树都为空->情况2
(2).当bro结点的左子树存在（记作left）且为黑色并且left的左子树为红色，left右子树存在且为黑色或者left右子树不存在->情况3
(3).当bro结点的左子树存在（记作left）且为黑色并且left的右子树为红色->情况4

2，brother结点为黑色，且其左右子树都是黑色或者左右子树都为空。
(1)parent节点是红色

对于这种情况需要将bro结点变为红色，parent结点变为黑色，这样在局部的这颗子树内部使其重新恢复平衡，直接返回（代码中就是break，因为后面还要做删除结点的工作），不用再做调整。

（2）parent节点的黑色

对于parent结点是黑色的情况，同样需要将bro结点颜色变红，这样才能使得parent结点的左右子树平衡（每条路径上黑色结点的数目一致）。但是在这颗局部的树中不能使得红黑树重新恢复平衡，所以需要继续向上调整（del = del->parent）
注意： 这里的继续向上调整，让del = del->parent不是说将要删除的结点修改，因为现在做的是调整过程不是删除过程， 让del = del->parent意思是以del->parent为根的子树的每条路径上黑色结点的数目比其他路径上的数目要少，要继续调整。（这很重要，不要理解错误）。并且其向上调整时可能转化为 1 2 3 4 中其中任意一种。

注： 红色圆圈没有上色表示颜色任意。

3，brother结点为黑色，且其左孩子为红色，右孩子为黑色，或者有孩子为空。

首先将bro的颜色改为红色，将bro的左子树的颜色改为黑色，然后对bro为根的子树进行一次右旋。这种情况就会转化为下面的情况4。

4，brother结点为黑色，且其右子树为红色。

对于这种情况，将bro右子树的颜色变为黑色，将bro结点颜色变为parent结点的颜色，将parent结点颜色改为黑色。但后对parent为根节点的子树左旋。在这样的子树内部调整完后，使得红黑树重新回复平衡，不需再继续调整。（代码中体现为break，因为后序还有删除操作，目前为调整操作）。

至此，删除结点为其父节点的左子树的情况已经全部分析完，删除结点为其父节点的右子树的情况与其类似，就不再叙述。

红黑树删除代码

bool erase(const pair<K, V>& kv)
{//1.找到要删除的位置node* del = _root;node* delParent = nullptr;while (del){if (del->_kv.first > kv.first){delParent = del;del = del->_left;}else if (del->_kv.first < kv.first){delParent = del;del = del->_right;}else{//找到了if (del->_left == nullptr) //只有一个子结点{if (del == _root){_root = _root->_right;if (_root){_root->_parent = nullptr;_root->_col = BLACK;}delete del;return true;}break;}else if (del->_right == nullptr){if (del == _root){_root = _root->_left;if (_root){_root->_parent = nullptr;_root->_col = BLACK;}delete del;return true;}break;}else{//左右子树都不为空，那么就要找个替死鬼node* minRight = del->_right;node* minPrev = del;while (minRight->_left){minPrev = minRight;minRight = minRight->_left;}del->_kv = minRight->_kv;del = minRight;delParent = del->_parent;break;}}}//没找到if (del == nullptr){return false;}node* delPos = del;node* delP = del->_parent;//调整红黑树if (del->_col == BLACK){if (del->_left){del->_left->_col = BLACK;}else if (del->_right){del->_right->_col = BLACK;}else //删除的是叶子结点{while (del != _root){if (del == delParent->_left){//情况1：bro结点是红色if (delParent && delParent->_right && delParent->_right->_col == RED){delParent->_col = RED;delParent->_right->_col = BLACK;RotateL(delParent);delParent = del->_parent;}//情况2：bro黑色并且其左右子树都是黑色或者都是nullptrif (delParent && delParent->_right && delParent->_right->_col == BLACK && 		((delParent->_right->_left == nullptr || delParent->_right->_left->_col == BLACK)
&& (delParent->_right->_right == nullptr || delParent->_right->_right->_col == BLACK)))/*if (delParent && delParent->_right && delParent->_right->_col == BLACK && ((delParent->_right->_left == nullptr && delParent->_right->_right == nullptr)
|| (delParent->_right->_left->_col == BLACK && delParent->_right->_right->_col == BLACK)))*/{if (delParent->_col == RED){delParent->_right->_col = RED;delParent->_col = BLACK;break;}else{delParent->_right->_col = RED;del = delParent;delParent = del->_parent;}}else{//情况3：bro为黑色，并且其左孩子为红色，有孩子为空或黑色if (delParent && delParent->_right && delParent->_right->_col == BLACK &&delParent->_right->_left && delParent->_right->_left->_col == RED&& (delParent->_right->_right == nullptr || delParent->_right->_right->_col == BLACK)){delParent->_right->_left->_col = BLACK;delParent->_right->_col = RED;RotateR(delParent->_right);}//情况4：bro为黑色，并且其右孩子是红色的delParent->_right->_right->_col = BLACK;delParent->_right->_col = delParent->_col;delParent->_col = BLACK;RotateL(delParent);delParent = del->_parent;break;}}else{//情况1：bro结点是红色if (delParent && delParent->_left && delParent->_left->_col == RED){delParent->_col = RED;delParent->_left->_col = BLACK;RotateR(delParent);delParent = del->_parent;}//情况2：bro黑色并且其左右子树都是黑色if (delParent && delParent->_left && delParent->_left->_col == BLACK && ((delParent->_left->_right == nullptr || delParent->_left->_right->_col == BLACK)&& (delParent->_left->_left == nullptr || delParent->_left->_left->_col == BLACK))){if (delParent->_col == RED){delParent->_left->_col = RED;delParent->_col = BLACK;break;}else{delParent->_left->_col = RED;del = delParent;delParent = del->_parent;}}else{//情况3：bro为黑色，并且其左孩子为红色，有孩子为空或黑色if (delParent && delParent->_left && delParent->_left->_col == BLACK &&delParent->_left->_right && delParent->_left->_right->_col == RED && (delParent->_left->_left == nullptr|| delParent->_left->_left->_col == BLACK)){delParent->_left->_right->_col = BLACK;delParent->_left->_col = RED;RotateL(delParent->_left);}//情况4：bro为黑色，并且其右孩子是红色的delParent->_left->_left->_col = BLACK;delParent->_left->_col = delParent->_col;delParent->_col = BLACK;RotateR(delParent);delParent = del->_parent;break;}}}}}//删除红黑树结点del = delPos;delParent = del->_parent;if (del->_left == nullptr){if (del == delParent->_left){delParent->_left = del->_right;}else{delParent->_right = del->_right;}if (del->_right){del->_right->_parent = del->_parent;}}else{if (del == delParent->_left){delParent->_left = del->_left;}else{delParent->_right = del->_left;}if (del->_left){del->_left->_parent = del->_parent;}}delete del;return true;
}

代码分析：

截图中注释掉的代码是一个很坑的地方，情况2为bro为黑色，且其左右子树都为黑色，或者都是空树，注释的代码就是这个意思，注释掉的原因是因为，与下面的情况不兼容，由于情况2的代码是写在情况3和4上面的，所以如果调整的情况为3或者4，那么必先经过情况2的 if 判断，因为i情况3 4 中bro的左右节点中可能存在空的情况，在情况2的 if 判断时会出现空指针的解引用问题。所以，截图中未注释掉的代码巧妙的兼容了下面的3 4 情况。

四，红黑树与AVL树的比较

🚀红黑树与AVL树都是高效的二叉搜索树，它们的增删改查的时间复杂度都是O（logN），但是它们的区别是控制平衡的方式不同：
AVL树：采用平衡因子的方式（每个结点的平衡因子的绝对值不大于1），使得AVL是一颗高度平衡的二叉搜索树。
红黑树：采用颜色控制的方式，红黑树最长路径的结点个数不超过最短路径结点个数的2倍，所以红黑树是近似平衡的。

红黑树降低了在插入和删除时旋转的次数，所以在实际使用时红黑树的效率是更优的，并且红黑树的实现相对简单一些，所以红黑树的应用场景更广泛。