前言
本文着重讲解红黑树的原理和性质及其难点。
以下是本篇文章正文内容
一、什么是红黑树？
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
也就是说，红黑树任意一条节点的路径长度都不超过最短路径的2倍。
二、红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的（反过来说，不能有连续的红色节点出现）
- 每一条路径的黑色节点数量均相同
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
为什么满足了上述性质，这棵红黑树就满足最长路径不超过最短路径的2倍？
在极限情况下，最短路径是全黑的路径，最长路径是一黑一红相间的路径，其余的每条路径的长度就是介于这两个节点的路径长度之间。所以只要符合上述性质，一定能满足最长路径不超过最短路径的2倍。
三、红黑书节点的定义
enum Colour { RED, BLACK }; template<class K, class V> struct RBTreeNode { public: RBTreeNode(const pair<K,V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_col(RED) {} RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; pair<K, V> _kv; Colour _col; };
四、红黑树的插入操作
- 1）找到待插入位置
由于红黑树也是一棵二叉搜索树，所以如果插入节点的值比根小，则向左走；如果插入节点的值比根大，则向右走。
注意这里有一些细节：
- 1）新插入的节点一定是红色的。
- 如果新插入节点是黑色的，则会违反性质4，会影响到整棵树，影响到每一条路径黑色节点数量是否相等。
- 如果新插入节点是红色的，假如插入节点的父亲是红色的，则违反性质3，在后续进行变色调整即可，如果插入节点的父亲是黑色的，则没有影响，直接就可以结束插入操作。
- 2）插入完成后，判断还是否符合红黑树的性质
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
下面的情况是p在g的左的情况。
情况1：变色
- 1.如果cur为红，p为红，u存在且为红，则需要进行变色。
将p和u从红色变成黑色，再让g由黑色变成红色。
注意，这里有一个细节，这棵树有可能只是一棵局部的树，也就是说，g可能还有父亲。
如果g的父亲是红色，则让cur走到g的位置，p走到g的父亲的位置，继续向上调整。
如果g的父亲是黑色，则结束了，退出。
如果g没有父亲（g是根节点），让g再变回黑色即可。
情况2：旋转+变色
- 2.如果cur为红，p为红，u不存在/u存在且为黑
下面是u存在且为黑的情况
2.1） 如果cur是p的左孩子，此时的情况就是单纯的左边高，对g进行右旋，最后变色即可。
具体的旋转过程参考上一篇文章AVL树的旋转，所有旋转细节都已经讲清楚了。
变色前：
cur是红的，p是红的，g是黑的，u是黑的
变色后：
cur是红的，p是黑的，g是红的，u是黑的
注意这里的细节：如果旋转前g有父亲，则旋转后需要让p指向g之前的父亲。
下面是u不存在的情况：
u不存在就更简单了，操作过程同上。
如果cur是p的右孩子，此时的情况就是折线形，也就是下面的情况：
此时需要进行左右双旋。
1.对p进行左旋后，再对g进行右旋，最后变色即可。
变色前：cur是红，p是红，g是黑。
变色后：cur是黑，p是红，g是红。
u不存在就更简单了，操作过程同上。
注意这里的细节：如果旋转前g有父亲，则旋转后需要让p指向g之前的父亲。
如果是p在g的右的情况
每种情况都是一样的，只不过是方向变了，照葫芦画瓢即可。
总结：
重点是看u（叔叔）节点
如果p是g的左的情况：
- 情况1：变色
- 1）如果cur为红，p为红，u存在且为红，则需要进行变色。
- 情况2：旋转+变色
- 1）如果cur为红，p为红，u不存在/u存在且为黑
- 如果cur是p的左，则为单纯的左边高，对g进行右旋后，再进行变色即可。
- 如果cur是p的右，则为折线形，先对p进行左旋，再对g进行右旋，最后进行变色即可。
红黑树插入节点代码
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; } Node* cur = _root; Node* cur_parent = _root; //1.找到待插入位置 while (cur) { if (cur->_kv.first < kv.first) { cur_parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { cur_parent = cur; cur = cur->_left; } else return false; } //2.先判断待插入节点是在parent的左边还是右边 cur = new Node(kv); //新插入的节点必须是红的 cur->_col = RED; if (cur_parent->_kv.first > kv.first) { cur_parent->_left = cur; } else { cur_parent->_right = cur; } //连接parent cur->_parent = cur_parent; //开始判断是否还符合红黑树的性质 while (cur_parent && cur_parent ->_col == RED) { Node* grandfather = cur_parent->_parent; //左边的情况 if (grandfather->_left == cur_parent) { Node* uncle = grandfather->_right; //u存在且为红 if (uncle && uncle->_col == RED) { cur_parent->_col = uncle->_col = BLACK; grandfather->_col = RED; Node* ppNode = grandfather->_parent; if (ppNode == nullptr) { grandfather->_col = BLACK; //g是根，变色后可以break了 break; } //向上调整 else if (ppNode->_col == RED) { cur = grandfather; cur_parent = ppNode; } else { //ppNode是黑色，已经完成了，可以break break; } } //u不存在/u存在且为黑 else { //单纯左边高，右单旋 if (cur == cur_parent->_left) { RotateR(grandfather); //变色 cur_parent->_col = BLACK; grandfather->_col = RED; } //折线形 // g // p // c else { RotateL(cur_parent); RotateR(grandfather); //变色 cur->_col = BLACK; grandfather->_col = RED; } //旋转+变色后，一定平衡了，可以break了 break; } } //右边的情况 // g g // p 或 p // c c else { Node* uncle = grandfather->_left; //u存在且为红 if (uncle && uncle->_col == RED) { cur_parent->_col = uncle->_col = BLACK; grandfather->_col = RED; Node* ppNode = grandfather->_parent; //1.ppNode为空 if (ppNode == nullptr) { grandfather->_col = BLACK; //g是根，变色后可以break了 break; } //2.ppNode存在且为红 //向上调整 else if (ppNode->_col == RED) { cur = grandfather; cur_parent = ppNode; } else { //ppNode是黑色，已经完成了，可以break break; } } //u不存在/u存在且为黑 // g g // p 或 p // c c else { //单纯右边高，左单旋 if (cur == cur_parent->_right) { RotateL(grandfather); //变色 cur_parent->_col = BLACK; grandfather->_col = RED; } //折线形 // g // p // c else { RotateR(cur_parent); RotateL(grandfather); //变色 cur->_col = BLACK; grandfather->_col = RED; } //旋转+变色后，一定平衡了，可以break了 break; } } } //不管发生什么样的情况，这个代码一定没有错 _root->_col = BLACK; return true; } //左单旋 void RotateL(Node* parent) { ++CountRotate; Node* cur = parent->_right; Node* curleft = cur->_left; //这个是cur的左子树，旋转后变成了parent的右孩子 Node* ppNode = parent->_parent; parent->_right = curleft; if (curleft) curleft->_parent = parent; cur->_left = parent; parent->_parent = cur; if (!ppNode) { _root = cur; cur->_parent = nullptr; } else { if (ppNode->_right == parent) { ppNode->_right = cur; } else { ppNode->_left = cur; } cur->_parent = ppNode; } } //右单旋 void RotateR(Node* parent) { ++CountRotate; Node* cur = parent->_left; Node* curright = cur->_right; Node* ppNode = parent->_parent; parent->_left = curright; //如果cur的右子树是空 if (curright) curright->_parent = parent; cur->_right = parent; parent->_parent = cur; if (!ppNode) { _root = cur; cur->_parent = nullptr; } else { cur->_parent = ppNode; //要知道根的左边是cur还是右边是cur if (ppNode->_left == parent) { ppNode->_left = cur; } else { ppNode->_right = cur; } } } void RotateLR(Node* parent) { Node* cur = parent->_left; Node* curright = cur->_right; RotateL(parent->_left); RotateR(parent); } void RotateRL(Node* parent) { Node* cur = parent->_right; Node* curleft = cur->_left; RotateR(parent->_right); RotateL(parent); }
五、验证一棵树是否为红黑树
- 1）验证中序遍历是否是有序序列
- 2）验证红黑树的各个性质
int Height() { return _Height(_root); } bool IsRBTree() { cout << "IsRBTree():"; return _IsRBTree(_root); } //判断一棵树是否为红黑树 //1.判断他的中序遍历 //2.判断红黑树的每一个性质 bool _IsRBTree(Node* root) { if (root == nullptr) { return true; } //性质1，每个节点不是红就是黑，不用判断 //性质2，根为黑 if (root->_col == RED) { cout << "根不是黑色的，不是红黑树" << endl; return false; } //检测3和4 //性质3 //不能出现连续的红节点 //性质4 //每条路径上的黑色节点个数相同 int benchmark = 0; Node* benchNode = root; //基准路径选最左边 while (benchNode) { if (benchNode->_col == BLACK) ++benchmark; benchNode = benchNode->_left; } if (!CheckColour(root,0,benchmark)) { return false; } return true; } //检验性质3，检验自己和父亲的颜色比检验自己和左右孩子的颜色更方便 //检验性质4，先随便求一条路径的黑色节点，然后再求其他路径的节点 //跟这条基准路径对比，不匹配就不符合性质4 //就算基准路径求出来是错的，其他路径是对的，如果两者对不上，那就不是红黑树 bool CheckColour(Node* root,int blacknum,int benchmark) { if (root == nullptr) { if (blacknum != benchmark) return false; return true; } if (root->_col == BLACK) ++blacknum; if (root->_col == RED && root->_parent && root->_parent->_col == RED) { cout << "出现了连续的红节点，不是红黑树" << endl; return false; } return CheckColour(root->_left,blacknum,benchmark) && CheckColour(root->_right, blacknum, benchmark); } int _Height(Node* root) { if (root == nullptr) return 0; int left = _Height(root->_left); int right = _Height(root->_right); return left > right ? left + 1 : right + 1; }
六、比较AVL树和红黑树
| 红黑树 | AVL树 | |
| 时间复杂度 | O(logN) | O(logN) |
| 树有10亿个值时 | 查找2*logN->60次 | 查找logN->30次 |
可见，红黑树和AVL树的查找次数是在同一个量级的，但由于AVL树要保持绝对平衡，所以需要更频繁地旋转操作。
当我用一千万个随机数进行测试时，结果如下：
AVL树的旋转次数在400多万次左右，红黑树的旋转次数在300多万，相差了几十万次，这里就体现出了差距。
不过，如果插入的数据是有序的，则AVL树的效率相对更高一点：
插入的数越随机，红黑树的效率越占优势。
所以实际上，红黑树的效率是比AVL树的效率要高一些的。实际中更多应用的也是红黑树
总结
这篇文章主要讲述对红黑树的插入操作，在插入节点后需要保证红黑树的性质，所以引出了变色，旋转+变色等操作。
