C++ 红黑树的概念、规则与实现

概述

红黑树是一种自平衡的二叉搜索树，通过引入节点颜色（红色和黑色）来维护平衡性。相比 AVL 树，红黑树对平衡的控制较松，旋转次数更少，适合写操作频繁的场景。

1. 红黑树的概念

红黑树的每个节点增加一个存储位来表示节点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。

1.2 红黑树的规则

每一个节点不是红色就是黑色。
根节点是黑色的。
任意一条路径不会有连续的红色节点，也就是说一个节点如果是红色的，那么它的孩子只能是黑色的。
对于任意一个节点，从该节点到其所有叶子节点的简单路径上，必须含有数量相同的黑色节点。

这些性质保证了红黑树的高度不会超过 log₂n，从而确保了良好的性能。

红黑树示例

说明：《算法导论》等书籍补充了一条每个叶子节点 (NIL) 都是黑色的规则。这里所指的叶子节点不是传统意义上的叶子节点，而是空节点，有些书籍上也把 NIL 叫做外部节点。NIL 是为了方便准确地标识出所有路径。

1.3 红黑树如何确保最长路径不超过最短路径的两倍？

由规则 4 可知，从根到叶子节点的每条路径都有相同数量的黑色节点，所以极端场景下，最短路径就是全是黑色节点的路径，假设最短路径长度为 bh (black height)。

由规则 2 和规则 3 可知，任意一条路径不会有连续的红⾊节点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为 2*bh。

综合红黑树的 4 点规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到叶子节点路径的长度为 x，那么 bh <= h <= 2*bh。

红黑树路径分析

1.4 红黑树的效率

假设 N 是红黑树中节点数量，h 最短路径的长度，那么 2h - 1 <= N < 2^(2*h) - 1，由此推出 h ≈ log₂N，也就意味着红黑树增删查改最坏也就是走最长路径 2 * log₂N，那么时间复杂度还是 O(logN)。

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

红黑树与 AVL 对比

2. 红黑树的实现

2.1 红黑树的结构

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

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

// 这里我们默认按 key/value 结构实现
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 红黑树的插入

插入一个值按二叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的 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，继续往上更新。

情况 1 变色

分析：因为 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 从黑色变成红色，更新上来的。

情况 2 单旋

分析上图左侧 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 为新增节点：

hb=0

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

情况 3：双旋 + 变色

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

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

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

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

双旋 1

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

双旋 2

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

这里用左右双旋演示：

左右双旋

代码演示

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

// 旋转代码的实现跟 AVL 树是一样的，只是不需要更新平衡因子
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 = 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;
}

2.3 红黑树的查找

按二叉搜索树逻辑实现即可，搜索效率为 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;
}

红黑树的删除操作相对复杂，因为它需要在删除节点后维护红黑树的特性。与插入一样都需要维护节点的颜色并且还要维护树的平衡，因此此处省略详细实现。

3. 红黑树的验证

那么我们如何去判断一棵树是否是红黑树呢？或者说在插入或者删除后如何检测该树是否还是红黑树。

如果只是获取最长路径和最短路径，检查最长路径不超过最短路径的 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);
}

4. 红黑树与 AVL 树

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

特性	AVL 树	红黑树
平衡条件	每个节点的左右子树高度差最多为 1	每条从根到叶子的路径上，黑色节点数相同，且不允许两个连续的红色节点
树的高度	更严格平衡，树高度较低，接近于 log₂n	平衡条件较松，树高度较 AVL 树略高，接近于 2*log₂n
旋转次数	插入和删除时旋转次数较多	插入和删除时旋转次数较少
实现复杂度	实现相对复杂，需要维护节点的高度或平衡因子	实现较复杂，需要维护节点的颜色属性
查找效率	查找效率较高，因为树高度更低	查找效率稍低，但仍为对数时间复杂度
删除操作性能	删除较复杂，可能引起多次旋转	删除相对简单，旋转次数较少

红黑树的优点：

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

AVL 树的优点：

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

概述

1. 红黑树的概念

1.2 红黑树的规则

每一个节点不是红色就是黑色。
根节点是黑色的。
任意一条路径不会有连续的红色节点，也就是说一个节点如果是红色的，那么它的孩子只能是黑色的。
对于任意一个节点，从该节点到其所有叶子节点的简单路径上，必须含有数量相同的黑色节点。

这些性质保证了红黑树的高度不会超过 log₂n，从而确保了良好的性能。

红黑树示例

说明：《算法导论》等书籍补充了一条每个叶子节点 (NIL) 都是黑色的规则。这里所指的叶子节点不是传统意义上的叶子节点，而是空节点，有些书籍上也把 NIL 叫做外部节点。NIL 是为了方便准确地标识出所有路径。

1.3 红黑树如何确保最长路径不超过最短路径的两倍？

由规则 2 和规则 3 可知，任意一条路径不会有连续的红⾊节点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为 2*bh。

红黑树路径分析

1.4 红黑树的效率

红黑树与 AVL 对比

2. 红黑树的实现

2.1 红黑树的结构

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

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

// 这里我们默认按 key/value 结构实现
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 红黑树的插入

插入一个值按二叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的 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，继续往上更新。

情况 1 变色

如果 g 的父亲还是红色，那么就还需要继续处理；
如果 g 的父亲是黑色，则处理结束了；
如果 g 就是整棵树的根，再把 g 变回黑色。

情况 1 只变色，不旋转。所以无论 c 是 p 的左还是右，p 是 g 的左还是右，都是上面的变色处理方式。

情况 2：单旋 + 变色

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

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

情况 2 单旋

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

左单旋

右单旋

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

抽象子树

旋转后变色

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

hb=0

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

情况 3：双旋 + 变色

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

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

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

双旋 1

双旋 2

这里用左右双旋演示：

左右双旋

代码演示

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

// 旋转代码的实现跟 AVL 树是一样的，只是不需要更新平衡因子
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 = 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;
}

2.3 红黑树的查找

按二叉搜索树逻辑实现即可，搜索效率为 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;
}

红黑树的删除操作相对复杂，因为它需要在删除节点后维护红黑树的特性。与插入一样都需要维护节点的颜色并且还要维护树的平衡，因此此处省略详细实现。

3. 红黑树的验证

那么我们如何去判断一棵树是否是红黑树呢？或者说在插入或者删除后如何检测该树是否还是红黑树。

所以我们还是去检查 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);
}

4. 红黑树与 AVL 树

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

特性	AVL 树	红黑树
平衡条件	每个节点的左右子树高度差最多为 1	每条从根到叶子的路径上，黑色节点数相同，且不允许两个连续的红色节点
树的高度	更严格平衡，树高度较低，接近于 log₂n	平衡条件较松，树高度较 AVL 树略高，接近于 2*log₂n
旋转次数	插入和删除时旋转次数较多	插入和删除时旋转次数较少
实现复杂度	实现相对复杂，需要维护节点的高度或平衡因子	实现较复杂，需要维护节点的颜色属性
查找效率	查找效率较高，因为树高度更低	查找效率稍低，但仍为对数时间复杂度
删除操作性能	删除较复杂，可能引起多次旋转	删除相对简单，旋转次数较少

红黑树的优点：

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

AVL 树的优点：

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

C++ 红黑树的概念、规则与实现

概述

1. 红黑树的概念

1.2 红黑树的规则

1.3 红黑树如何确保最长路径不超过最短路径的两倍？

1.4 红黑树的效率

2. 红黑树的实现

2.1 红黑树的结构

2.2 红黑树的插入

情况 1：变色

情况 2：单旋 + 变色

情况 3：双旋 + 变色

代码演示

2.3 红黑树的查找

3. 红黑树的验证

4. 红黑树与 AVL 树

C++ 红黑树的概念、规则与实现

概述

1. 红黑树的概念

1.2 红黑树的规则

1.3 红黑树如何确保最长路径不超过最短路径的两倍？

1.4 红黑树的效率

2. 红黑树的实现

2.1 红黑树的结构

2.2 红黑树的插入

情况 1：变色

情况 2：单旋 + 变色

情况 3：双旋 + 变色

代码演示

2.3 红黑树的查找

3. 红黑树的验证

4. 红黑树与 AVL 树

更多推荐文章

相关免费在线工具

更多推荐文章

相关免费在线工具

C++ 红黑树的概念、规则与实现

概述

1. 红黑树的概念

1.2 红黑树的规则

1.3 红黑树如何确保最长路径不超过最短路径的两倍？

1.4 红黑树的效率

2. 红黑树的实现

2.1 红黑树的结构

2.2 红黑树的插入

情况 1：变色

情况 2：单旋 + 变色

情况 3：双旋 + 变色

代码演示

2.3 红黑树的查找

3. 红黑树的验证

4. 红黑树与 AVL 树

C++ 红黑树的概念、规则与实现

概述

1. 红黑树的概念

1.2 红黑树的规则

1.3 红黑树如何确保最长路径不超过最短路径的两倍？

1.4 红黑树的效率

2. 红黑树的实现

2.1 红黑树的结构

2.2 红黑树的插入

情况 1：变色

情况 2：单旋 + 变色

情况 3：双旋 + 变色

代码演示

2.3 红黑树的查找

3. 红黑树的验证

4. 红黑树与 AVL 树

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具