C++ 红黑树实现详解：概念、规则与代码

// 红黑树结点
template<class K, class V>
struct RBTreeNode {
    // 这里更新控制平衡也要加入 parent 指针
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;
    
    // 构造函数
    RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};

最后：在实现红黑树的整体结构

enum Colour { RED, BLACK };
// 红黑树结点
template<class K, class V>
struct RBTreeNode {
    // 这里更新控制平衡也要加入 parent 指针
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;
    
    RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};

template<class K, class V>
class RBtree {
    typedef RBTreeNode<K, V> Node;
public:
    // 功能实现 ---------------------------------------------------------------------------------
private:
    Node* _root = nullptr;
};

2.2 红黑树插入

2.2.1 红黑树树插入一个值的大概过程

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

搜索树的插入规则：

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

2. 如果是空树插入，新增结点是黑色结点。如果是非空树插入，新增结点必须红色结点，因为非空树插入，新增黑色结点就破坏了规则 4，规则 4 是很难维护的。

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

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

2.2.2 变色

说明： 下图中假设我们把新增结点标识为 c (cur)，c 的父亲标识为 p (parent)，p 的父亲标识为 g (grandparent)，p 的兄弟标识为 u (uncle)。

c 为红，p 为红，g 为黑，u 存在且为红，则将 p 和 u 变黑，g 变红。在把 g 当做新的 c，继续往上更新。 分析： 因为 p 和 u 都是红色，g 是黑色，把 p 和 u 变黑，左边子树路径各增加一个黑色结点，g 再变红，相当于保持 g 所在子树的黑色结点的数量不变，同时解决了 c 和 p 连续红色结点的问题，需要继续往上更新是因为，g 是红色，如果 g 的父亲还是红色，那么就还需要继续处理；如果 g 的父亲是黑色，则处理结束了；如果 g 就是整棵树的根，再把 g 变回黑色。 情况 1 只变色，不旋转。所以无论 c 是 p 的左还是右，p 是 g 的左还是右，都是上面的变色处理方式。

插入一个新结点 c 必须为红色，而需要变色的情况为：

parent 为红
g grandparent 为黑
cur 为红
这三个结点颜色是固定的

那么就取决于 uncle 的颜色： 若 uncle 存在且 uncle 为红：那么就变色处理

• 根据黑色结点个数进行 0 和 1 或以上个黑色结点进行变色 hb(黑色结点的个数)： hb = 0

hb != 0

总结：如果 uncle 存在且为红色，那么就需要变色处理，parent 变黑，uncle 变黑，grandparent 变红

代码实现:

// g
// p u
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED) {
    // 变色
    parent->_col = uncle->_col = BLACK;
    grandparent->_col = RED;
    // 继续往上处理
    cur = grandparent;
    parent = cur->_parent;
}

2.2.3 单旋 + 变色

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

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

在左边： --------------------------g ----------p------------------------------u c

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

在右边： ------------------g --------u-------------------p -----------------------------------c

先旋转在变色，parent 变黑，grandparent 变红 代码实现：

if (cur == parent->_left) {
    // g
    // p u
    // c
    RotateR(grandparent);
    parent->_col = BLACK;
    grandparent->_col = RED;
}

2.2.4 双旋 + 变色

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

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

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

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

双旋在变色：grandparent 变红，cur 变黑。

代码实现:

else {
    // g
    // u p
    // c
    // 需双旋 + 变色
    RotateR(parent);
    RotateL(grandparent);
    cur->_col = BLACK;
    grandparent->_col = RED;
}

2.3 红黑树的插入代码实现

enum Colour { RED, BLACK };
// 红黑树结点
template<class K, class V>
struct RBTreeNode {
    // 这里更新控制平衡也要加入 parent 指针
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;
    
    RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};

// 红黑树
template<class K, class V>
class RBtree {
    typedef RBTreeNode<K, V> Node;
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 (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* grandparent = parent->_parent;
            if (parent == grandparent->_left) {
                // g
                // p u
                Node* uncle = grandparent->_right;
                if (uncle && uncle->_col == RED) {
                    // 变色
                    parent->_col = uncle->_col = BLACK;
                    grandparent->_col = RED;
                    // 继续往上处理
                    cur = grandparent;
                    parent = cur->_parent;
                } else {
                    if (cur == parent->_left) {
                        // g
                        // p u
                        // c
                        RotateR(grandparent);
                        parent->_col = BLACK;
                        grandparent->_col = RED;
                    } else {
                        // g
                        // p u
                        // c
                        RotateL(parent);
                        RotateR(grandparent);
                        cur->_col = BLACK;
                        grandparent->_col = RED;
                    }
                    break;
                }
            } else {
                Node* uncle = grandparent->_left;
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandparent->_col = RED;
                    // 继续往上处理
                    cur = grandparent;
                    parent = cur->_parent;
                } else {
                    // 旋转 + 变色
                    if (cur == parent->_right) {
                        // g
                        // u p
                        // c
                        RotateL(grandparent);
                        parent->_col = BLACK;
                        grandparent->_col = RED;
                    } else {
                        // g
                        // u p
                        // c
                        // 需双旋 + 变色
                        RotateR(parent);
                        RotateL(grandparent);
                        cur->_col = BLACK;
                        grandparent->_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* parentParent = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;
        if (parent == _root) {
            _root = subR;
            subR->_parent = nullptr;
        } else {
            if (parent == parentParent->_left) {
                parentParent->_left = subR;
            } else {
                parentParent->_right = subR;
            }
            subR->_parent = parentParent;
        }
    }
    
    void RotateR(Node* parent) {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR) subLR->_parent = parent;
        Node* pParent = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;
        if (parent == _root) {
            _root = subL;
            subL->_parent = nullptr;
        } else {
            if (pParent->_left == parent) {
                pParent->_left = subL;
            } else {
                pParent->_right = subL;
            }
            subL->_parent = pParent;
        }
    }
private:
    Node* _root = nullptr;
};

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 红黑树的验证

这里获取最长路径和最短路径，检查最长路径不超过最短路径的 2 倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查 4 点规则，满足这 4 点规则，一定能保证最长路径不超过最短路径的 2 倍。

1. 规则 1 枚举颜色类型，天然实现保证了颜色不是黑色就是红色。
2. 规则 2 直接检查根即可
3. 规则 3 前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲的颜色就方便多了。
4. 规则 4 前序遍历，遍历过程中用形参记录跟到当前结点的 blackNum(黑色结点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值，依次比较即可。

代码实现：

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 << "存在连续红节点" << endl;
        return false;
    }
    if (root->_col == BLACK) {
        blackNum++;
    }
    return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}