C++ 红黑树原理与实现

2.2 红黑树的插入

插入的大概过程：

我们假设新增结点为 c,c 的父结点为 p，p 的父亲标示为 g，p 的兄弟标示为 u

①：插入一个值按二叉搜索树的规则进行插入，插入后我们只需要观察是否符合红黑树的四条规则

②：如果是空树插入，新增结点是黑色结点，如果是非空树插入，则新增结点必须是红色结点，因为非空树插入新增一个黑色结点会破坏规则四，规则四很难维护，

③：非空树插入后，新增结点必须是红色结点，如果父亲结点是黑色的，则没有违反任何规则，插入结束

④：非空树插入后，新增结点必须是红色结点，如果父亲结点是红色的，则违反了规则 3，进一步分析：c 是红色，p 为红，g 必为黑，这三个颜色都固定了，关键变化是 u，我们需要根据 u 的情况分情况处理：

2.2.1 情况 1：变色

插入的结点 c 为红色，c 的父结点 p 也是红色，p 的父结点 g 为黑，p 的兄弟 u 存在且为红，把 p 和 u 变黑，g 变红，再把 g 当做新的 c，继续往上更新

分析：因为 p 和 u 都是红色，g 是黑色，，把 p 和 u 变黑，左边子树路径各增加一个黑色结点，g 再变红，相当于保持 g 所在子树的黑色结点数量不变，同时解决了 c 和 p 连续红色的问题，需要继续往上更新是因为：g 是红色，如果 g 的父亲还是红色，那么就需要我们继续处理，如果 g 的父亲是黑色，则处理结束了，如果 g 就是整棵树的根，我们再把 g 变回黑色

情况一只变色，而不旋转，所以无论 c 是 p 的左还是右，都是上面的变色处理：

我们这里只是展示了一种具体的情况，但实际中需要这样处理的有很多情况

现在我们可以将上面类似的处理进行抽象表达，d/e/f 代表每条路径拥有 hb 个黑色结点的子树，

a/b 代表每条路径拥有 hb-1 个黑色结点的根为红的子树

2.2.2 情况 2：单旋 + 变色

新插入的结点 c 是红色，c 的父结点 p 为黑色，u 不存在或者 u 存在且为黑色，u 不存在则 c 一定是新增结点，u 存在且为黑，则 c 一定不是新增的，c 之前是黑色的，是在 c 的子树中插入，符合情况一，变色将 c 从黑色变成红色，更新上来的

分析：p 必须为黑，才能解决，连续红色结点的问题，u 不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转 + 变色

如果 p 是 g 的左，c 是 p 的左，那么以 g 为旋转点进行单右旋，再把p 变成黑，g 变成红即可，p 变成这棵树的根，这样子树黑色结点的数量不变，没有连续的红的结点，且不需要往上更新，因为 p 的父亲是黑色还是红色都不违反规则

如果 p 是 g 的右，c 是 p 的右，那么以 g 为旋转点进行左单旋，再把p 变黑，g 变红即可，p 变成这棵树的根，这样子树黑色结点的数量不变，没有连续的红色结点，且不再需要继续往上更新，因为同样 p 的父亲时候红色还是黑色都不会违反规则

2.2.3 情况 3：双旋 + 变色

c 为红，p 为红，p 为黑，u 不存在或者 u 存在且为黑，u 不存在，则 c 一定是新增结点，u 存在且为黑，则 c 一定不是新增，c 之前是黑色的，是在 c 的子树中插入，符合情况 1，变色将 c 从黑色变红色，更新上来的

分析：p 必须变为黑才能解决，连续红色结点的问题，u 不存在或者是黑色的，同样的，这里单纯的变色无法解决问题，需要旋转 + 变色

如果 p 是 g 的左，c 是 p 的右，那么先以 p 为旋转点进行左单旋，再以 g 为旋转点进行右单旋，再把 c 变黑，g 变红即可，c 变成这棵树新的根，这样子树黑色结点的数量不变，没有连续的红色结点，且不需要再往上更新，因为 c 的父亲是黑色还是红色或者空都不违反规则

如果 p 是 g 的右，c 是 p 的左，那么先以 p 为旋转点进行单右旋，再以 g 为旋转点进行左单旋，再把 c 变黑，g 变红即可，c 变成这棵树的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要再往上更新，因为 c 的父亲是黑色还是红色或者空都不违反规则

2.3 红黑树的插入代码实现

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; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; // g // p u if (parent == grandfather->_left) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { //uncle 存在且为红色，只需要我们变色再继续往上处理 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { //uncle 不存在，这时需要我们旋转加变色解决 if (cur == parent->_left) { // g // p u //c //此时右单旋即可 RotateR(grandfather); //变色的规则：p 变黑，g 变红 parent->_col = BLACK; grandfather->_col = RED; } else { // g // p u // c //此时要双旋才能解决（左右双旋） RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { // g // u p Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { //叔叔存在且为红，只需要变色即可 // g // u p parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上处理 cur = grandfather; parent = cur->_parent; } else { //叔叔不存在或者存在且为黑 //当存在且为黑时 // g // u p // c if (cur == parent->_right) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // u p // c RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; }

2.4 红黑树的查找

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

2.5 红黑树的验证

bool Check(Node* root, int blackNum, const int refNum) { if (root == nullptr) { //前序遍历走到头，说明一条路径走完了 if (refNum != blackNum) { cout << "存在黑色结点的数量不等的路径" << endl; return false; } return true; } if (root->_col == RED && root->_parent->_col == RED) { cout << root->_kv.first << "存在连续的红色结点" << endl; return false; } if (root->_col == BLACK) { blackNum++; } return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum); }
bool IsBalance() { if (_root == nullptr) return true; if (_root->_col == RED) return false; int refNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { ++refNum; } cur = cur->_left; } return Check(_root, 0, refNum); }