C++红黑树原理与实现

表格总结：

四、红黑树框架的搭建

#pragma once
#include <iostream>
using namespace std;
enum Colour {
    RED,
    BLACK
};
template<class K, class V>
struct RBTreeNode {
    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),_col(RED){}
};
template<class K, class V>
class RBTree {
    typedef RBTreeNode<K, V> Node;
public:
private:
    Node* _root = nullptr;
};

五、红黑树的插入逻辑

1. 大体框架

首先，插入逻辑的答题思路是和前面我们所学的 AVL 树的插入主体框架是大体相同的，代码如下：

bool Insert(const pair<K, V>& kv) {
    // 树为空，直接插入然后返回
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur) {
        // 小于往左走
        if (kv.first < cur->_kv.first) {
            parent = cur;
            cur = cur->_left;
        } else if (kv.first > cur->_kv.first) // 大于往右走
        {
            parent = cur;
            cur = cur->_right;
        } else {
            return false;
        }
    }
    cur = new Node(kv);
    // 链接
    if (cur->_kv.first < parent->_kv.first) {
        parent->_left = cur;
    } else {
        parent->_right = cur;
    }
    cur->_parent = parent;
    return true;
}

2. 初始颜色的设置

首先迎来我们第一个问题，新插入结点初始的颜色要设置成什么呢？

如果是根节点，答案很明确，根节点的颜色是黑色！

// 树为空，直接插入然后返回
if (_root == nullptr) {
    _root = new Node(kv);
    // 根节点必须是黑色
    _root->_col = BLACK;
    return true;
}

那么对于其他结点呢？ 是插入红色，还是插入黑色？

这里面就涉及到两个相冲的规则：

如果我们选择插入黑色，那么就会违背规则 4，那么画出的图是这样的：

就会造成所有路径黑色结点出现问题，就要更改所有路径的风险，因此我们不选择这种方案。

如果选择插入红色结点，就会违背规则 3，画出的图是这样的：

如果插入到红色节点后，则只牵扯到当前路径，很容易进行调整。因此我们新插入的结点默认为 红色！！！

所以对于其他颜色，我们调节的代码为：

cur = new Node(kv);
// 其他结点初始颜色为红色
cur->_col = RED;

3. 颜色的调整

1）通过具体的情况对颜色调整进行框架认识

对于颜色的调整，我们可以总结为三种情况：

情况一：uncle 存在，且为红色： 解决方式：parent 与 uncle 变黑，grandfather 变红，继续向上调整。

情况二：uncle 不存在 解决方式：旋转 + 变色

情况三：uncle 存在且为黑色 解决方式：旋转 + 变色

我们上一种情况继续插入，就会变成这种情况：

2）通过抽象图对颜色调整加深理解

情况一：uncle 存在且 uncle 为红色

代码解析：

// 如果我们 parent 是黑色，不用处理，就结束了
// 情况一：cur 为红，parent 为红，grandfather 为黑，uncle 不确定
// 用 while 循环是因为我们要不断的向上调整
while (parent && parent->_col == RED) {
    // 首先我们要找到 grandfather
    Node* grandfather = parent->_parent;
    // 接下来通过 grandfather 找到 uncle
    // 如果 parent 是 grandfather->_left
    if (parent == grandfather->_left) {
        // 说明 uncle 在右边
        Node* uncle = grandfather->_right;
        // uncle 存在且为红
        if (uncle && uncle->_col == RED) {
            // 满足上述情况，开始调整颜色
            parent->_col = BLACK;
            uncle->_col = BLACK;
            grandfather->_col = RED;
            // 继续向上调整
            cur = grandfather;
            parent = cur->_parent;
            // 但是走到这里有一个问题，如果当前 parent 就是根，
            // 并且 parent 是红色，我们要把它变为黑色，
            // 处理方式是：出循环后，暴力将_root->_col 变为黑色
        } else // uncle 不存在 或 uncle 存在且为黑色
        {
            // ...
        }
    }
    // 这里保证根为黑色
    _root->_col = BLACK;
}

情况二：uncle 不存在或 uncle 存在且 uncle 为黑色

因为这里牵扯到旋转，所以我们需要知道旋转的逻辑，这个之前做过专题讲解过，不会的小伙伴可以参考相关资料。

下面我们在这里再放以下旋转的代码~ 唯一的区别就是，这里不需要平衡因子。

// 左单旋
void RotateL(Node* parent) {
    Node* cur = parent->_right;
    Node* curleft = cur->_left;
    // 重新链接
    parent->_right = curleft;
    if (curleft) // 如果 curleft 存在
    {
        curleft->_parent = parent;
    }
    cur->_left = parent;
    Node* ppnode = parent->_parent;
    parent->_parent = cur;
    if (ppnode == nullptr) {
        _root = cur;
        cur->_parent = nullptr;
    } else {
        if (ppnode->_left == parent) {
            ppnode->_left = cur;
        } else {
            ppnode->_right = cur;
        }
        cur->_parent = ppnode;
    }
}
// 右单旋
void RotateR(Node* parent) {
    Node* cur = parent->_left;
    Node* curright = cur->_right;
    parent->_left = curright;
    if (curright) {
        curright->_parent = parent;
    }
    cur->_right = parent;
    Node* ppnode = parent->_parent;
    parent->_parent = cur;
    if (ppnode == nullptr) {
        cur->_parent = nullptr;
        _root = cur;
    } else {
        if (ppnode->_left == parent) {
            ppnode->_left = cur;
        } else {
            ppnode->_right = cur;
        }
        cur->_parent = ppnode;
    }
}

代码解析：

} else // uncle 不存在 或 uncle 存在且为黑色
{
    // 判断要怎样旋转
    // 右单旋
    if (cur == parent->_left) {
        // g
        // p
        // c
        RotateR(grandfather);
        // 调整颜色
        parent->_col = BLACK;
        grandfather->_col = RED;
    } else // 左右双旋
    {
        // g
        // p
        // c
        RotateL(parent);
        RotateR(grandfather);
        // 调整颜色
        cur->_col = BLACK;
        grandfather->_col = RED;
    }
    // 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出
    break;
}

六、红黑树是否构建正确的检查

以下的这段代码的核心目标是检查红黑树是否构建正确，主要基于红黑树的规则进行验证。代码的设计分为两个关键部分：计算基准值和递归验证规则。

代码解析

// 检查是否构建正确
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 << root->_kv.first << "出现连续红色节点" << endl;
        return false;
    }
    return CheckColour(root->_left, blacknum, benchmark) && CheckColour(root->_right, blacknum, benchmark);
}
bool IsBalance() {
    return IsBalance(_root);
}
bool IsBalance(Node* root) {
    if (root == nullptr)
        return true;
    if (root->_col != BLACK) {
        return false;
    }
    // 基准值
    int benchmark = 0;
    Node* cur = _root;
    while (cur) {
        if (cur->_col == BLACK)
            ++benchmark;
        cur = cur->_left;
    }
    return CheckColour(root, 0, benchmark);
}

1. 基准值的计算 在红黑树中，所有从根节点到叶节点的路径上，必须经过相同数量的黑色节点。为此，代码首先沿着树的左侧路径计算路径上黑色节点的数量，作为基准值 benchmark。这是验证红黑树平衡性的关键步骤。
2. 递归验证红黑树规则 接下来通过递归函数 CheckColour，对红黑树的所有节点进行逐一验证，确保其符合以下规则：
3. 每个节点是红色或黑色。
4. 红色节点的子节点必须是黑色（即不能出现连续的红色节点）。
5. 从任一节点到其所有后代的每条路径包含相同数量的黑色节点。

整体逻辑描述

• 首先调用 IsBalance()，对整棵树进行平衡性检查。
  • 先判断根节点是否为黑色，这是红黑树的基本要求。
  • 沿着左侧路径，计算从根节点到最左叶节点的黑色节点总数，作为基准值。
• 然后进入递归检查函数 CheckColour()：
  • 如果当前节点为空（即到达叶节点），检查该路径累计的黑色节点数量是否与基准值一致。
  • 对每个非空节点，检查其颜色是否满足规则：红色节点不能有红色父节点。
  • 累计当前路径上的黑色节点数，并递归检查左右子树。
• 最终通过递归结果判断整棵树是否满足红黑树性质。
• 如果发现不符合的地方（如连续红色节点或黑色节点数不一致），会提前返回 false 并结束验证。

我们运行的时候给 10000000 个随机值，看看会不会调用成功。

#include "RBTree_1.h"
#include <vector>
int main() {
    const int N = 10000000;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; i) {
        v.push_back(i);
    }
    RBTree<int, int> rbt;
    for (auto e : v) {
        rbt.Insert(make_pair(e, e));
    }
    cout << rbt.IsBalance() << endl;
    return 0;
}

运行结果如下：

说明我们的红黑树构建成功啦~

七、红黑树总体代码总结

#pragma once
#include <iostream>
using namespace std;
enum Colour {
    RED,
    BLACK
};
template<class K, class V>
struct RBTreeNode {
    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),_col(RED){}
};
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 (kv.first < cur->_kv.first) {
                parent = cur;
                cur = cur->_left;
            } else if (kv.first > cur->_kv.first) // 大于往右走
            {
                parent = cur;
                cur = cur->_right;
            } else {
                return false;
            }
        }
        cur = new Node(kv);
        // 其他结点初始颜色为红色
        cur->_col = RED;
        // 链接
        if (cur->_kv.first < parent->_kv.first) {
            parent->_left = cur;
        } else {
            parent->_right = cur;
        }
        cur->_parent = parent;
        // 如果我们 parent 是黑色，不用处理，就结束了
        // 情况一：cur 为红，parent 为红，grandfather 为黑，uncle 不确定
        // 用 while 循环是因为我们要不断的向上调整
        while (parent && parent->_col == RED) {
            // 首先我们要找到 grandfather
            Node* grandfather = parent->_parent;
            // 接下来通过 grandfather 找到 uncle
            // 如果 parent 是 grandfather->_left
            if (parent == grandfather->_left) {
                // 说明 uncle 在右边
                Node* uncle = grandfather->_right;
                // uncle 存在且为红
                if (uncle && uncle->_col == RED) {
                    // 满足上述情况，开始调整颜色
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 继续向上调整
                    cur = grandfather;
                    parent = cur->_parent;
                    // 但是走到这里有一个问题，如果当前 parent 就是根，
                    // 并且 parent 是红色，我们要把它变为黑色，
                    // 处理方式是：出循环后，暴力将_root->_col 变为黑色
                } else // uncle 不存在 或 uncle 存在且为黑色
                {
                    // 判断要怎样旋转
                    // 右单旋
                    if (cur == parent->_left) {
                        // g
                        // p
                        // c
                        RotateR(grandfather);
                        // 调整颜色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else // 左右双旋
                    {
                        // g
                        // p
                        // c
                        RotateL(parent);
                        RotateR(grandfather);
                        // 调整颜色
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    // 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出
                    break;
                }
            } else //(parent == grandfather->_right) // 如果 parent 是 grandfather->_right
            {
                // 说明 uncle 在左边
                Node* uncle = grandfather->_left;
                // uncle 存在且为红
                if (uncle && uncle->_col == RED) {
                    // 满足上述情况，开始调整颜色
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 继续向上调整
                    cur = grandfather;
                    parent = cur->_parent;
                } else // uncle 不存在 或 uncle 存在且为黑色
                {
                    // 判断要怎样旋转
                    // 左单旋
                    if (cur == parent->_right) {
                        // g
                        // p
                        // c
                        RotateL(grandfather);
                        // 调整颜色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else // 右左双旋
                    {
                        // g
                        // p
                        // c
                        RotateR(parent);
                        RotateL(grandfather);
                        // 调整颜色
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        // 这里保证根为黑色
        _root->_col = BLACK;
        return true;
    }
    // 左单旋
    void RotateL(Node* parent) {
        Node* cur = parent->_right;
        Node* curleft = cur->_left;
        // 重新链接
        parent->_right = curleft;
        if (curleft) // 如果 curleft 存在
        {
            curleft->_parent = parent;
        }
        cur->_left = parent;
        Node* ppnode = parent->_parent;
        parent->_parent = cur;
        if (ppnode == nullptr) {
            _root = cur;
            cur->_parent = nullptr;
        } else {
            if (ppnode->_left == parent) {
                ppnode->_left = cur;
            } else {
                ppnode->_right = cur;
            }
            cur->_parent = ppnode;
        }
    }
    // 右单旋
    void RotateR(Node* parent) {
        Node* cur = parent->_left;
        Node* curright = cur->_right;
        parent->_left = curright;
        if (curright) {
            curright->_parent = parent;
        }
        cur->_right = parent;
        Node* ppnode = parent->_parent;
        parent->_parent = cur;
        if (ppnode == nullptr) {
            cur->_parent = nullptr;
            _root = cur;
        } else {
            if (ppnode->_left == parent) {
                ppnode->_left = cur;
            } else {
                ppnode->_right = cur;
            }
            cur->_parent = ppnode;
        }
    }
    // 检查是否构建正确
    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 << root->_kv.first << "出现连续红色节点" << endl;
            return false;
        }
        return CheckColour(root->_left, blacknum, benchmark) && CheckColour(root->_right, blacknum, benchmark);
    }
    bool IsBalance() {
        return IsBalance(_root);
    }
    bool IsBalance(Node* root) {
        if (root == nullptr)
            return true;
        if (root->_col != BLACK) {
            return false;
        }
        // 基准值
        int benchmark = 0;
        Node* cur = _root;
        while (cur) {
            if (cur->_col == BLACK)
                ++benchmark;
            cur = cur->_left;
        }
        return CheckColour(root, 0, benchmark);
    }
private:
    Node* _root = nullptr;
};