C++ 红黑树详解：原理、实现与验证

红黑树的表达相对 AVL 树要抽象一些，AVL 树通过高度差直观地控制了平衡。红黑树通过 4 条规则的颜色约束，间接地实现了近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的节点，红黑树的旋转次数是更少的，因为它对平衡的控制没那么严格。

红黑树的实现

红黑树的结构

红黑树与 AVL 树的结构基本上相似，只是 AVL 树中的每个节点的平衡因子改为了红黑树中每个节点的颜色。

// 枚举值表示颜色
enum Colour {
    RED,
    BLACK
};

// 这里我们默认按 key/value 结构实现
template<class K, class V>
struct RBTreeNode {
    // 这里更新控制平衡也要加入 parent 指针
    std::pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;

    RBTreeNode(const std::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;
};

红黑树的插入

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

为了满足规则 1，在空树插入时，新增节点必须是黑色节点。如果是非空树插入，新增节点必须红色节点，因为非空树插入，新增黑色节点就破坏了规则 4，规则 4 是很难维护的。

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

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

情况 1：变色

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 的左还是右，都是上面的变色处理方式。

情况 2：单旋 + 变色

c 为红且与 p 在同一条斜线上，p 为红，g 为黑，u 不存在或者 u 存在且为黑

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

分析上图中左侧 u 不存在可知，u 不存在，所以以 g 节点到每一个叶子节点的黑色节点数目为 1，而 c 若不是新插入的节点，则代表它是由情况 1 变色而来的，说明在以 c 为根节点的子树中还一定存在黑色节点，此时不符合红黑树的规则 4，因此如果 u 不存在，那么 c 一定是新增节点。同理，右侧如果 c 是新增节点，同样不符合规则 4，因此如果 u 存在且为黑色，那么 c 一定不是新增节点。

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

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

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

这里的旋转与 AVL 树中的旋转一模一样，只是不再需要更新平衡因子。

无论 c 是否为新增节点，都不会影响我们的单旋 + 变色操作，与 AVL 树一样，对于旋转我们需要将一些子树给抽象出来，在 AVL 树中对于这些抽象出来的子树我们只需要知道它们的高度即可，而在红黑树中，我们需要知道这些抽象出来的子树中黑色节点的数量 hb。

例如上图，我们需要对 g 节点进行右单旋：将 g 变为 p 的右，d 变为 g 的左，p 成为新的根，与 AVL 树中的右单旋一模一样。只是在红黑树中，我们进行了右单旋后还需要进行变色：旋转完后将 p 变为黑色，g 变为红色：

当 hb==0 时，也就是 u 不存在时，也就是 c 为新增节点：

至于左单旋不再详细介绍，思路与右单旋一样。

情况 2：双旋 + 变色

c 为红且与 p 不在同一条斜线上，p 为红，g 为黑，u 不存在或者 u 存在且为黑

• 与单旋 + 变色相同，u 不存在，则 c 一定是新增节点，u 存在且为黑，则 c 一定不是新增节点。

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

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

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

其实我们可以发现，无论是红黑树还是 AVL 树，它们进行单旋还是双旋的逻辑是一样的。有了前面 AVL 树中的旋转基础，这里我们就不再过多解释，直接用图来带大家理解：

这里用左右双旋演示：

代码演示

下面让我们看一看具体的插入代码：

// 旋转代码的实现跟 AVL 树是一样的，只是不需要更新平衡因子
bool Insert(const std::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 = parent->_right;
        } else if (cur->_kv.first > kv.first) {
            parent = cur;
            cur = parent->_left;
        } else {
            return false;
        }
    }
    cur = new Node(kv); // 新增结点。颜色给红色
    cur->_col = RED;
    if (parent->_kv.first > kv.first) {
        parent->_left = cur;
    } else {
        parent->_right = cur;
    }
    cur->_parent = parent;

    while (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        if (parent == grandfather->_left) {
            Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED) {
                // u 存在且为红 -> 变色再继续往上处理
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                // u 存在且为黑或不存在 -> 单旋 + 变色
                // g
                // p u
                // c
                if (cur == parent->_left) {
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    // 双旋 + 变色
                    // g
                    // p u
                    // c
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        } else {
            Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == RED) {
                // u 存在且为红 -> 变色再继续往上处理
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                // u 存在且为黑或不存在 -> 单旋 + 变色
                // g
                // u p
                // c
                if (cur == parent->_right) {
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    // 双旋 + 变色
                    // g
                    // u p
                    // c
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    _root->_col = BLACK;
    return true;
}

红黑树的查找

按二叉搜索树逻辑实现即可，搜索效率为 O(logN)

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 倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。

所以我们还是去检查 4 点规则，满足这 4 点规则，一定能保证最长路径不超过最短路径的 2 倍。

• 规则 1 枚举颜色类型，天然实现保证了颜色不是黑色就是红色。
• 规则 2 直接检查根即可。
• 规则 3 前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲的顏色就方便多了。

规则 4 前序遍历，遍历过程中用形参记录跟到当前结点的 blackNum(黑色结点数量)，前序遍历遇到黑色结点就 ++blackNum，走到空就计算出了一条路径的黑色结点数量。再以任意一条路径黑色结点数量作为参考值，依次比较即可。

下面让我们看一看具体的代码实现：

bool Check(Node* root, int blackNum, const int refNum) {
    if (root == nullptr) {
        // 前序遍历走到空时，意味着一条路径走完了
        // cout << blackNum << endl;
        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);
}

红黑树与 AVL 树

红黑树和 AVL 树都是自平衡二叉搜索树，那它们之间有什么区别呢？

红黑树的优点：

• 插入和删除效率较高：旋转次数较少，写操作性能较好，适合写操作较频繁的场景。
• 实现灵活：由于平衡条件较松，实现和维护相对灵活。
• 广泛应用：许多库和语言（如 Linux 内核、Java 的 TreeMap 等）使用红黑树作为底层数据结构。

AVL 树的优点：

• 查询性能优越：由于其严格的平衡条件，AVL 树的高度最小，查询操作速度更快，适合读操作多于写操作的场景。
• 平衡维护严格：高度差保证在 1 以内，保证了高度的最小化。