一、红黑树的概念
红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，这句话换个意思就是：红黑树中最长路径不超过最短路径的 2 倍。因而是接近平衡的，而 AVL 树是严格平衡的，这就导致，红黑树的高度会比 AVL 树高一些，但是效率并不会比 AVL 树差。
二、红黑树的性质
- 每个结点不是红色就是黑色。
- 根节点是黑色。
- 如果一个结点是红色，则它的两个孩子结点必须是黑色的。
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
- 每个
NIL叶子结点都是黑色的（此处的叶子结点指的是空节点）。
小Tips：第三点决定了一颗红黑树的任何路径没有连续的红色结点。在红黑树中计算路径一定是计算到 NIL 结点。一颗红黑树中的最短路径是全为黑结点的路径，最长路径是一黑一红相间的路径。任意一条路径上黑色结点的占比一定是大于等于 1 / 2 1/21/2 的。这就决定了，红黑树中其最长路径中结点个数不会超过最短路径结点个数的两倍。
三、红黑树结点的定义
//红黑树的结点 template<class K, class V> struct RBTreeNode { RBTreeNode(const& pair<K, V> kv = pair<K, V>(), Color color = RED) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_col(color) {} pair<K, V> _kv;//结点中存的值 RBTreeNode<K, V>* _left;//结点的左孩子 RBTreeNode<K, V>* _right;//结点的右孩子 RBTreeNode<K, V>* _parent;//结点的父亲 Color _col;//结点的颜色 };
小Tips：新节点默认颜色是 RED。这是因为，如果新插入结点的颜色是 BLACK，那意味着当前路径上新增了一个黑色结点，为了保证二叉树的第四条性质，我们要对这颗红黑树其他的所有路径进行检查，可见新插入结点如果默认是 BLACK，会存在着牵一发而动全身的影响。而让新插入结点默认是 RED 则不会出现这样的结果。假如新插入结点的 parent 恰好是 BLACK，那这次插入就没有什么问题。如果新插入结点是 parent 是 RED，此时需要对这颗红黑树稍作调整。
四、红黑树的插入操作
红黑树是在二叉搜索树的基础上加上平衡限制条件，因此红黑树的插入可以分为两步：
- 按照二叉搜索树的规则插入结点。
- 检测新节点插入后，红黑树的性质是否遭到破坏。
因为新结点的默认颜色是 RED，因此：如果其双亲结点的颜色是 BLACK，没有违反红黑树任何性质，则不需要调整；但是当新插入节点的双亲结点颜色为 RED 时，就违反了性质三不能有连在一起的红色结点，此时需要对红黑树分情况来讨论：
约定：cur为当前结点，parent 为父结点，grandp 为祖父结点，uncle 为叔叔结点。如果 parent 为红那 grandp 一定为黑。所以当前唯一不确定的就是 uncle，主要分以下三种情况
4.1 情况一：uncle 存在且为红
小Tips：此处看到的树，可能是一颗完整的树，也可能是一颗子树。
解决方式：将 parent 和 uncle 改为黑，grandp 改成红。然后把 grandp 当成 cur，继续向上调整。
- 如果
grandp是根结点，将grandp再改成黑色，本次插入就算结束。 - 如果
grandp是子树，则其一定也有双亲，且grandp的双亲如果是红色，需要继续向上调整。
4.2 情况二：uncle 不存在
如果 uncle 结点不存在，则 cur 一定是新插入结点，因为如果 cur 不是新插入结点，则 cur 和 parent 一定有一个结点的颜色是黑色，就不满足性质四：每条路径黑色结点个数相同。
解决方法：直接进行旋转即可。
4.3 情况三：uncle 存在且为黑
叔叔存在且为黑，那么 cur 一定不是新插入的结点，并且 cur 结点原来的颜色一定是黑色，现在看到是红色的原因是因为 cur 的子树在调整的过程中将 cur 结点的颜色由黑色改成了红色。
4.4 插入完整源码
public: 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 (kv.first < cur->_kv.first)//小于往左走 { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first)//大于往右走 { parent = cur; cur = cur->_right; } else//相等插入不了 { return false; } } //找到待插入位置了，进行插入 cur = new Node(kv); cur->_col = RED; if (kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; //检测新结点插入后，红黑树的性质是否遭到破坏 while (parent && parent->_col == RED) { Node* grandp = parent->_parent; if (parent == grandp->_left) { Node* uncle = grandp->_right; if (uncle && uncle->_col == RED)//叔叔存在且为红 { parent->_col = BLACK; uncle->_col = BLACK; grandp->_col = RED; //继续向上处理 cur = grandp; parent = cur->_parent; } else //uncle不存在或者存在为黑 { if (cur == parent->_left) { RotateR(grandp); parent->_col = BLACK;//parent当了根 grandp->_col = RED; } else if (cur == parent->_right) { RotateLR(grandp); cur->_col = BLACK;//cur当了根节点 grandp->_col = RED; } break; } } else if (parent == grandp->_right) { Node* uncle = grandp->_left; if (uncle && uncle->_col == RED)//叔叔存在且为红 { parent->_col = BLACK; uncle->_col = BLACK; grandp->_col = RED; //继续向上处理 cur = grandp; parent = cur->_parent; } else //uncle不存在或者存在为黑 { if (cur == parent->_right) { RotateL(grandp); parent->_col = BLACK;//parent当了根 grandp->_col = RED; } else if (cur == parent->_left) { RotateRL(grandp); cur->_col = BLACK;//cur当了根节点 grandp->_col = RED; } break; } } } _root->_col = BLACK;//根结点始终变黑 return true; } private: //左单旋 void RotateL(Node* parent) { ++_rotatecount; Node* cur = parent->_right; Node* curleft = cur->_left; parent->_right = curleft; cur->_left = parent; if (curleft) { curleft->_parent = parent; } Node* ppnode = parent->_parent; parent->_parent = cur; if (parent == _root) { _root = cur; cur->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } cur->_parent = ppnode; } } //右单旋 void RotateR(Node* parent) { ++_rotatecount; Node* cur = parent->_left; Node* curright = cur->_right;//此时的情况是curright比cur大，比parent小 parent->_left = curright; cur->_right = parent; if (curright) { curright->_parent = parent; } Node* ppnode = parent->_parent; parent->_parent = cur; if (ppnode) { cur->_parent = ppnode; if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } } else { _root = cur; cur->_parent = nullptr; } } //右左双旋 void RotateRL(Node* parent) { Node* cur = parent->_right; Node* curleft = cur->_left; RotateR(parent->_right); RotateL(parent); } //左右双旋 void RotateLR(Node* parent) { Node* cur = parent->_left; Node* curright = cur->_right; RotateL(cur); RotateR(parent); }
五、红黑树的验证
红黑树的检测分为两步：
- 检测其是否满足二叉搜索树（中序遍历是否为有序序列）。
- 检测其是否满足红黑树的性质（主要是性质三和性质四）。
public: bool Isblance() { if (_root == nullptr) return true; //根节点如果不是黑色说明就不是红黑树 if (_root->_col != BLACK) { return false; } //计算红黑树中任意一条路径上黑色结点的个数作为一个基准值 Node* cur = _root; int count = 0; while (cur) { if (cur->_col == BLACK) { ++count; } cur = cur->_left; } return CheckColour(_root, 0, count); } private: //检查颜色 bool CheckColour(Node* root, int blacknum, int stand) { if (root == nullptr) { //到这里说明一条路径结束，那么这条路径上的黑色结点数也一定统计出来了 if (blacknum != stand) { cout << "当前路径上黑色结点的个数有问题" << endl; return false; } return true; } //检查是否出现连续的红色结点 if (root->_col == RED && root->_parent && root->_parent->_col == RED) { cout << root->_kv.first << ":为红色节点，并且孩子结点也是红色" << endl; } //统计一条路径上黑色结点个数 if (root->_col == BLACK) { ++blacknum; } return CheckColour(root->_left, blacknum, stand) && CheckColour(root->_right, blacknum, stand); }
六、红黑树与 AVL 树的比较
红黑树和 AVL 树都是高效的平衡二叉树，增删查改的时间复杂度都是 O ( l o g 2 N ) O(log2^N)O(log2N)，红黑树不追求绝对平衡，其只需要保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入过程中旋转的次数，所以在经常进行增删查改的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。红黑树主要会应用在以下几个地方：
- C++ STL 库----map、set、mutilmap、mutilset。
- Java 库。
- Linux 内核。
- 其它一些库。
七、结语
今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，春人的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！
