红黑树的概念

红黑树的性质

红黑树节点的定义

红黑树的结构

红黑树的插入操作

情况一

情况二

情况三

红黑树的验证

红黑树的查找

红黑树与AVL树的比较

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。

红黑树的性质

红黑树为了保证其最长路径中节点个数不会超过最短路径节点个数的两倍，具有以下性质：

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

根据红黑树的性质3可以得出，红黑树当中不会出现连续的红色结点，而根据性质4又可以得出，从某一结点到其后代叶子结点的所有路径上包含的黑色结点的数目是相同的。

我们假设在红黑树中，从根到叶子的所有路径上包含的黑色结点的个数都是N个，那么最短路径就是全部由黑色节点构成的路径，即长度为N。

而最长可能路径就是由一黑一红结点构成的路径，该路径当中黑色结点与红色结点的数目相同，即长度为2N。

因此，红黑树从根到叶子的最长可能路径不会超过最短可能路径的两倍。

红黑树节点的定义

template<class K, class V>
struct RBTreeNode
{//三叉链//方便旋转操作RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;//存储的键值对pair<K, V> _kv;//结点的颜色int _col; //红/黑//构造函数RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

对于节点的颜色，因为只有红和黑两种颜色，bool值表示比较简单，但这里我使用枚举定义颜色，可以增加代码的可读性和可维护性，并且便于后序的调试操作。

//枚举定义结点的颜色
enum Colour
{RED,BLACK
};

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

当我们向红黑树插入结点时，若我们插入的是黑色结点，那么插入路径上黑色结点的数目就比其他路径上黑色结点的数目多了一个，即破坏了红黑树的性质4，此时我们就需要对红黑树进行调整。

若我们插入红黑树的结点是红色的，此时如果其父结点也是红色的，那么表明出现了连续的红色结点，即破坏了红黑树的性质3，此时我们需要对红黑树进行调整；但如果其父结点是黑色的，那我们就无需对红黑树进行调整，插入后仍满足红黑树的要求。

插入黑色结点，一定破坏红黑树的性质4，必须对红黑树进行调整。插入红色结点，可能破坏红黑树的性质3，可能对红黑树进行调整。因此，我们在构造结点进行插入时，应该默认将结点的颜色设置为红色。

红黑树的结构

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

红黑树的插入操作

红黑树的插入操作与二叉搜索树插入结点时的逻辑相同，可以分为三个步骤，红黑树的关键在于第三步对红黑树的调整。

按二叉搜索树的插入方法，找到待插入位置。
将待插入结点插入到树中。
若插入结点的父结点是红色的，则需要对红黑树进行调整。

红黑树在插入结点后是如何调整的？

实际上，在插入结点后并不是一定会对红黑树进行调整，若插入结点的父结点是黑色的，那么我们就不用对红黑树进行调整，因为本次结点的插入并没有破坏红黑树的五点性质。（这也是为什么我们默认将待插入的节点设置为红色）

只有当插入结点的父结点是红色时才需要对红黑树进行调整，因为我们默认插入的结点就是红色的，如果插入结点的父结点也是红色的，那么此时就出现了连续的红色结点，因此需要对红黑树进行调整。

因为插入结点的父结点是红色的，说明父结点不是根结点（根结点是黑色的），因此插入结点的祖父结点（父结点的父结点）就一定存在。

红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况。

【约定】:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一

cur为红，p为红，g为黑，u存在且为红

此时为了避免出现连续的红色结点，我们可以将父结点变黑，但为了保持每条路径黑色结点的数目不变，因此我们还需要将祖父结点变红，再将叔叔变黑。这样一来既保持了每条路径黑色结点的数目不变，也解决了连续红色结点的问题。

但调整还没有结束，因为此时祖父结点变成了红色，如果祖父结点是根结点，那我们直接再将祖父结点变成黑色即可，此时相当于每条路径黑色结点的数目都增加了一个。

但如果祖父结点不是根结点的话，我们就需要将祖父结点当作新插入的结点，再判断其父结点是否为红色，若其父结点也是红色，那么又需要根据其叔叔的不同，进而进行不同的调整操作。

因此，情况一的抽象图表示如下：

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

情况二

cur为红，p为红，g为黑，u不存在/u存在且为黑

u存在且为黑的情况一定是在情况一继续往上调整的过程中出现的，即这种情况下的cur结点一定不是新插入的结点，而是上一次情况一调整过程中的祖父结点，如下图：

我们将路径中祖父结点之上黑色结点的数目设为X,将叔叔结点之下黑色结点的数目设为Y，则在插入结点前，图示两条路径黑色结点的数目分别为X+1和X+2+Y，很明显左右两条路径的黑色节点不同，因此在插入结点前就不满足红黑树的要求了，所以说叔叔结点存在且为黑这种情况，一定是由情况一往上调整过程中才会出现的一种情况。

出现叔叔存在且为黑时，单纯使用变色已经无法处理了，这时我们需要进行旋转处理。若祖孙三代的关系是直线（cur、parent、grandfather这三个结点为一条直线），则我们需要先进行单旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根结点是黑色的，因此无需继续往上进行处理。

【说明】u的情况有两种

如果u节点不存在，则cur一定是新插入的节点，因为如果cur不是新插入的节点，则cur和p一定有一个节点的颜色是黑色的，就不满足性质4。
如果u节点存在且是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到是红色的原因正如上面所说，cur的子树在调整的过程中将cur的颜色由黑色变成红色了。

解决方式：

p为g的左孩子，cur为p的左孩子，则进行右单旋转
p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色--p变黑，g变红

情况三

cur为红，p为红，g为黑，u不存在/u存在且为黑

情况三与情况二类似，只不过情况三是双旋，情况二是单旋

解决方式：

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

然后即可按照情况二处理

红黑树的验证

红黑树也是一种特殊的二叉搜索树，因此我们可以先获取二叉树的中序遍历序列，来判断该二叉树是否满足二叉搜索树的性质。

//中序遍历
void Inorder()
{_Inorder(_root);
}
//中序遍历子函数
void _Inorder(Node* root)
{if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);
}

但中序有序只能证明是二叉搜索树，要证明二叉树是红黑树还需验证该二叉树是否满足红黑树的性质。

//判断是否为红黑树
bool IsBalance()
{if (_root && _root->_col == RED){cout << "根节点颜色是红色" << endl;return false;}int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}// 连续红色节点return _Check(_root, 0, benchmark);
}bool _Check(Node* root, int blackNum, int benchmark)
{if (root == nullptr){if (benchmark != blackNum){cout << "某条路径黑色节点的数量不相等" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return _Check(root->_left, blackNum, benchmark)&& _Check(root->_right, blackNum, benchmark);
}

红黑树的查找

红黑树的查找函数与二叉搜索树的查找方式一模一样，逻辑如下：

若树为空树，则查找失败，返回nullptr。
若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
若key值等于当前结点的值，则查找成功，返回对应结点。

代码如下：

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 nullptr;
}