【C++】红黑树

---

红黑树的概念

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

红黑树的性质特征

1. 每个结点不是黑色就是红色；
2. 根节点_root是黑色；
3. 如果一个结点是红色的，则它的两个孩子结点是黑色的（即没有连续的红色结点，注意可以有连续的黑色结点）；
4. 对于每个结点，从该结点到其所有后代叶子的简单路径上，均包含相同数目的黑色结点（即每条路径上都包含相同数量黑色结点）；
5. 空节点，即NIL结点可以认为是黑色的，注意：计算有几条路径时，是要看是否走到空节点，即图上的NIL空节点，故如图的红黑树有5条路径；

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

红黑树是近似平衡，不能保证每次都完全平衡。由性质3可知红色结点不能连续，由性质4可得每条路径均包含相同数量的黑色结点。

若我们假设从根到叶子结点的路径中包含黑色结点的数量为N。
最短路径：全黑，长度为N,高度logN

最长路径：一黑一红相间，记住要保证每条路径包含的黑色结点个数是相同的，那么长度为2N,高度2logN

最优情况：
如果需要保证左右平衡，那么有可能是全黑 或者 每条路径都是一黑一红相间的路径（满二叉树）。
最差情况：
左子树全黑，右子树一黑一红

可以发现，最坏情况的时间复杂度和AVL树（严格平衡）一样，都是O(logN)，但是红黑树（“非严格平衡”）这种近似平衡的结构减少了大量旋转，综合性能优于AVL树。

红黑树结点的定义

红黑树的实现类似AVL树，我们采用KV模型实现红黑树，并采用三叉链结构，除此之外，我们需要引入一个新的成员变量表示：结点的颜色。这里我们采用枚举的方式定义结点颜色，这样可以增加代码的可读性和可维护性，便于后序操作。

//利用枚举定义颜色
enum colour
{RED,//0BLACK//1
};
//红黑树结点的定义
template <class K,class V>
struct RBTreeNode
{//<key,value>pair<K, V> _kv;//三叉链结构RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;//结点的颜色int _col;//构造函数RBTreeNode<K, V>(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){ }
};

为什么构造结点的时候，结点的颜色默认设置成红色？

我们先来回顾一下红黑树的性质3和性质4：没有连续的红色结点；每条路径上包含相同数量的黑色结点。

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

当我们向红黑树插入的是红色结点时，如果此时插入结点的父节点也是红色结点，那么就出现了连续的红色结点，这就会破坏性质3，此时我们需要对红黑树进行调整。如果父节点是黑色的，我们就不需要对红黑树进行调整。

即插入黑色结点，一定破坏红黑树的性质4，必须对红黑树进行调整。插入红色结点，可能会破坏红黑树的性质3，可能需要对红黑树进行调整。综合看来，插入红色结点更好。

红黑树的插入操作

红黑树一开始的插入操作跟AVL树一样，关键在于第三步。

1. 如果根节点为空，先创建一个根节点（注意红黑树根节点是黑色的）
2. 找到插入结点插入的位置
3. 如果插入结点的父节点是红色的，则需要对红黑树进行调整

红黑树在插入结点后，如何对红黑树进行调整？

如果插入结点的父节点是黑色的，则不需要对红黑树进行调整。（不破坏红黑树的性质）。

如果插入结点的父节点是红色的，则需要对红黑树进行调整，因为我们默认插入的结点颜色是红色的，这样就会出现连续的红色结点。

下面具体将红黑树的调整分成3种情况，重点关注插入结点的父节点，叔叔结点（即父节点的兄弟结点），祖父结点。

情况1

注意以下看到的树，可能是一棵完整的树，也可能是一棵子树，以下是抽象图的展示。

插入结点的父节点是红色，祖父结点是黑色，叔叔存在，且结点是红色。

调整方式：我们先观察调整之前的图形，这种情况下，插入新的结点之后，会出现连续的红色结点，并且从g开始，每条路径包含的黑色结点的数量为1。

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

相信同学们还有疑问，不是说根节点必须是黑色的吗，为什么颜色调整之后，根变成了红色呢？

不要急，因为调整还未结束。这种情况下祖父结点变成了红色，如果祖父结点是根结点，那么我们直接将祖父结点变成黑色即可。此时每条路径的保护的黑色结点又多了一个，调整之前每条路径的黑色结点是1个，现在每条路径包含的黑色结点是两个，依然满足性质4.

但如果祖父结点不是根结点，这棵树是一棵子树，那么我们就需要将祖父结点当作新插入的结点，再判断其父节点是否为红色，若父节点也是红色，那么需要根据叔叔的情况，进行不同的调整。

注意：插入结点的父节点为红，叔叔结点存在且为红时，cur结点无论是parent的左孩子还是右孩子，调整方式都是一样的。

情况2

插入结点的叔叔不存在，即插入结点的父节点的兄弟结点不存在。

若插入结点的叔叔不存在，那么cur一定是新插入的结点，而不是其它情况向上调整变化而来的，因为叔叔不存在，则p的孩子不可能存在黑色结点（遵循性质4）。

这种情况下，祖孙三代的关系是一条直线，我们需要先进行单旋操作，再进行颜色调整，颜色调整后，这棵子树的根节点变成了黑色，所以不需要再向上继续调整。

若p是g的左孩子，cur是p的左孩子，则这棵子树的左边较高，我们以p为轴点，进行右单旋，再将parent父节点改为黑色，祖父结点改为红色；

若p是g的右孩子，cur是p的左孩子，则这棵子树的右边较高，我们以p为轴点，进行左单旋，再将parent父节点改为黑色，祖父结点改为红色。

情况3

插入结点的叔叔存在。且叔叔结点为黑色。

这种情况下一定是上次情况一调整之后出现的，cur不可能是新插入的结点，否则就不遵循性质4，每条路径包含的黑色结点数量相同了。

这时单纯的变色无法直接解决问题，情况三是由情况2变化而来的，所以我们依然需要先进行单旋操作，再进行颜色调整，parent父节点改为黑色，祖父结点u改成红色，叔叔结点u依然保持黑色。颜色调整成功后，这棵子树的根节点是黑色的，所以无需继续向上进行调整。

同理：
若p是g的左孩子，cur是p的左孩子，则这棵子树的左边较高，我们以p为轴点，进行右单旋，再将parent父节点改为黑色，祖父结点改为红色；

若p是g的右孩子，cur是p的左孩子，则这棵子树的右边较高，我们以p为轴点，进行左单旋，再将parent父节点改为黑色，祖父结点改为红色。

注意：情况二和情况三都是先进行旋转操作，再进行颜色调整。并且调整成功后，这棵子树的根节点已经变成黑色，无需再进行向上调整。只有情况一，祖父结点被改成红色，才需要继续向上调整。

特殊情况

前面的情况123，parent，cur，grandparents,都是连成一条直线的。那么这个所谓的特殊情况，就是parent，cur，grandparents的路径从形状上看来，是一条折线。

若形状呈一条折线，那么有以下两种情况：

• parent在grandparents的左边，cur在parent的右边

解决方法：以parent为轴点先进行左单旋，再以g为轴点进行右单旋（即左右双旋），最后调整结点颜色，将cur变成黑色，将grandparents变成红色；

• parent在grandparents的右边，cur在parent的左边

解决方法：先以p为轴点进行右单旋，接着以g为轴点进行左单旋，最后调整结点颜色，将cur结点变成黑色，将g结点变成红色。

注意：除了情况一调整之后g结点会变成红色，需要继续向上调整，其它情况颜色调整完后，g（子树）根节点都会被调整成黑色，因此不需要继续向上调整。

代码实现

	bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;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;}else{return false;}}cur = new Node(kv);cur->_col = RED;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* grandfater = parent->_parent;if (parent == grandfater->_left){Node* uncle = grandfater->_right;// 情况一  uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;cur = grandfater;parent = cur->_parent;}else{if (cur == parent->_left){// 情况二RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{// 情况三RotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else // (parent == grandfater->_right){Node* uncle = grandfater->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;cur = grandfater;parent = cur->_parent;}else{//   g                //      p//         cif (cur == parent->_right){RotateL(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{//   g                //      p//   cRotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(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 (_root == parent)if (ppNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}

红黑树的验证

1.验证其是否为二叉搜索树（通过中序遍历）
2.验证其是否满足红黑树的性质，包括根节点为黑，不能出现连续的红色结点，每条路径包含的黑色结点的数量要相同。

    //中序遍历判断是否为二叉搜索树void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}bool Check(Node* root, int blackNum, const int ref){//root为空，意味着走到了空节点if (root == nullptr){//cout << blackNum << endl;if (blackNum != ref){cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;return false;}return true;}//出现连续的红色结点，则直接返回falseif (root->_col == RED && root->_parent->_col == RED){cout << "违反规则：出现连续红色节点" << endl;return false;}//统计路径中黑色结点的数量if (root->_col == BLACK){++blackNum;}return Check(root->_left, blackNum, ref)&& Check(root->_right, blackNum, ref);}bool IsBalance(){//空树也是平衡二叉树if (_root == nullptr){return true;}//如果根节点不是黑色，则直接返回falseif (_root->_col != BLACK){return false;}//ref是reference的缩写，翻译为参考//记录最左边黑色结点的数量int ref = 0;//以最左边的路径包含的黑色结点数量为参考值，进行各路径的比对Node* left = _root;while (left){if (left->_col == BLACK){++ref;}left = left->_left;}//利用check函数进行各条路径的比对return Check(_root, 0, ref);}

红黑树的删除

红黑树的删除本节不做讲解，有兴趣的同学可参考：《算法导论》或者《STL源码剖析》
链接

红黑树和AVL树的比较

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

红黑树的应用

1. C++ STL库 – map/set、mutil_map/mutil_set
2. Java 库
3. linux内核
4. 其他一些库