在数据结构中，二叉搜索树（BST）凭借 "左小右大" 的特性实现了高效的查找、插入操作，但它存在致命缺陷 —— 当插入有序数据（如 1,2,3,4,5）时，会退化为链表，导致操作时间复杂度从 O (logn) 暴跌至 O (n)。为解决这一问题，1972 年 Leo J. Guibas 和 Robert Sedgewick 提出了红黑树，它是一种自平衡二叉搜索树，通过 "颜色规则 + 旋转操作" 严格控制树的高度，确保树始终保持近似平衡，从而稳定维持高效性能。

本文将从红黑树的核心原理出发，逐步拆解节点设计、插入逻辑、平衡维护（旋转与变色）等关键模块，最后附上可直接运行的完整 C++ 代码，帮你彻底掌握这一经典数据结构。

一、红黑树的核心定义与特性

红黑树本质是近似平衡的二叉搜索树，它不仅满足 BST 的所有规则（左子树节点值 <根节点值，右子树节点值> 根节点值），还通过 5 条颜色规则强制树的高度保持在 O (logn) 级别：

1.1 五条核心规则

红黑树的 "平衡" 依赖于对节点颜色的严格约束，所有节点要么是红色，要么是黑色，且必须满足：

规则编号	规则描述	核心作用
1	每个节点要么是红色，要么是黑色	定义节点颜色取值范围
2	根节点必须是黑色	保证树的顶层稳定性
3	所有 NIL 节点（空节点，逻辑叶子）都是黑色	简化边界条件判断（代码中用nullptr替代）
4	若一个节点是红色，则其两个子节点必须是黑色	禁止连续红节点，避免局部失衡
5	从任意节点到其所有后代 NIL 节点的路径上，黑色节点数量相等	保证树的整体平衡性，限制树高

1.2 关键概念：黑高

"黑高" 是红黑树的核心指标，指从某节点到叶子节点路径上黑色节点的数量（不含当前节点）。根据规则 5，任意节点到所有叶子的黑高相等，这一特性直接限制了红黑树的高度 —— 最坏情况下高度不超过2log(n+1)，确保所有操作的时间复杂度稳定在 O (logn)。

二、红黑树的节点结构设计

红黑树的节点需要存储比普通 BST 更多的信息，以支持颜色管理和平衡维护。具体包括：

• 键值对（Key-Value）：实现字典式的键值映射；
• 左 / 右子节点指针：构建二叉树基本结构；
• 父节点指针：插入后需从子节点回溯到祖先节点调整平衡，父指针简化了这一过程；
• 颜色标识：标记节点为红色或黑色，用于判断是否违反规则。

基于 C++ 模板实现的节点结构如下：

// 定义节点颜色枚举：红黑树节点仅支持红、黑两种颜色
enum Colour {
    BLACK,  // 黑色节点
    RED     // 红色节点
};

// 模板参数k：键（Key）类型（需支持比较操作）
// 模板参数v：值（Value）类型（与键对应）
template<class k, class v>
struct RBTreeNode {
    pair<k, v> _kv;                  // 存储键值对（Key-Value）
    Colour _colour;                  // 节点颜色（BLACK/RED）
    RBTreeNode<k, v>* _left;         // 左子节点指针
    RBTreeNode<k, v>* _right;        // 右子节点指针
    RBTreeNode<k, v>* _parent;       // 父节点指针（用于回溯调整平衡）

    // 构造函数：初始化节点，默认红色（减少平衡调整次数）
    RBTreeNode(const pair<k, v>& kv)
        : _kv(kv)
        , _colour(RED)               // 新节点默认红色
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
    {}
};

三、红黑树的核心操作：插入与平衡维护

插入是红黑树最复杂的操作，需分为 **"查找插入位置"**"插入新节点"" 回溯判断失衡 ""通过变色 / 旋转恢复平衡" 四步，其中后两步是平衡维护的关键。

3.1 步骤 1：查找插入位置（遵循 BST 规则）

与普通 BST 一致，从根节点出发，根据键值大小向左 / 右子树遍历，直到找到空位置（插入点），同时记录插入节点的父节点。

// 查找插入位置
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
    if (cur->_kv.first > kv.first) {
        parent = cur;
        cur = cur->_left;  // 向左子树找
    } else if (cur->_kv.first < kv.first) {
        parent = cur;
        cur = cur->_right; // 向右子树找
    } else {
        return false; // 键已存在，插入失败
    }
}

3.2 步骤 2：插入新节点

创建新节点后，根据父节点的键值大小，将新节点连接为父节点的左 / 右孩子。若树为空，直接将新节点作为根，并设为黑色（满足规则 2）。

// 情况1：树为空，直接创建根节点（根节点必须为黑色）
if (_root == nullptr) {
    _root = new Node(kv);
    _root->_colour = BLACK;
    return true;
}

// 情况2：树非空，插入新节点
cur = new Node(kv);
cur->_parent = parent;  // 建立新节点到父节点的关联
if (parent->_kv.first > kv.first) {
    parent->_left = cur;  // 作为左孩子插入
} else {
    parent->_right = cur; // 作为右孩子插入
}

3.3 步骤 3：回溯判断失衡与修复

插入新节点后，仅当父节点为红色时才可能违反规则 4（连续红节点），此时需要从父节点开始向上回溯，结合祖父节点和叔叔节点的颜色，判断失衡场景并执行修复操作。

完整代码实现：

// 仅当父节点为红色时需调整（父节点为黑色不破坏任何规则）
while (parent && parent->_colour == RED) {
    Node* grandfather = parent->_parent; // 祖父节点（必为黑色）
    
    // 分场景处理：父节点是祖父的左孩子 / 右孩子（对称逻辑）
    if (grandfather->_left == parent) {
        // 场景1：父节点是祖父的左孩子（叔叔为祖父的右孩子）
        Node* uncle = grandfather->_right;
        // 子场景1.1：叔叔存在且为红色（单纯变色）
        if (uncle && uncle->_colour == RED) {
            parent->_colour = BLACK;    // 父节点变黑
            uncle->_colour = BLACK;     // 叔叔节点变黑
            grandfather->_colour = RED; // 祖父节点变红
            
            // 向上回溯：检查祖父节点与曾祖父的颜色
            cur = grandfather;
            parent = cur->_parent;
        }
        // 子场景1.2：叔叔不存在或为黑色，且cur是parent的左孩子（LL型）
        else if (cur == parent->_left) {
            revolveR(grandfather);       // 对祖父节点右旋
            parent->_colour = BLACK;     // 父节点变黑
            grandfather->_colour = RED;  // 祖父节点变红
            break; // 局部平衡，退出回溯
        }
        // 子场景1.3：叔叔不存在或为黑色，且cur是parent的右孩子（LR型）
        else {
            revolveL(parent);            // 先对父节点左旋
            revolveR(grandfather);       // 再对祖父节点右旋
            cur->_colour = BLACK;        // cur节点变黑
            grandfather->_colour = RED;  // 祖父节点变红
            break; // 局部平衡，退出回溯
        }
    } else {
        // 场景2：父节点是祖父的右孩子（叔叔为祖父的左孩子，与场景1对称）
        Node* uncle = grandfather->_left;
        // 子场景2.1：叔叔存在且为红色（单纯变色）
        if (uncle && uncle->_colour == RED) {
            parent->_colour = BLACK;    // 父节点变黑
            uncle->_colour = BLACK;     // 叔叔节点变黑
            grandfather->_colour = RED; // 祖父节点变红
            
            // 向上回溯：检查祖父节点与曾祖父的颜色
            cur = grandfather;
            parent = cur->_parent;
        }
        // 子场景2.2：叔叔不存在或为黑色，且cur是parent的右孩子（RR型）
        else if (cur == parent->_right) {
            revolveL(grandfather);       // 对祖父节点左旋
            parent->_colour = BLACK;     // 父节点变黑
            grandfather->_colour = RED;  // 祖父节点变红
            break; // 局部平衡，退出回溯
        }
        // 子场景2.3：叔叔不存在或为黑色，且cur是parent的左孩子（RL型）
        else {
            revolveR(parent);            // 先对父节点右旋
            revolveL(grandfather);       // 再对祖父节点左旋
            cur->_colour = BLACK;        // cur节点变黑
            grandfather->_colour = RED;  // 祖父节点变红
            break; // 局部平衡，退出回溯
        }
    }
}

// 最终确保根节点为黑色（调整过程可能导致根节点变色）
_root->_colour = BLACK;

3.4 步骤 4：旋转操作（核心平衡手段）

旋转是红黑树平衡维护的核心手段，分为左旋和右旋，两者逻辑对称，目的是通过调整节点位置，消除连续红节点并维持 BST 特性。

右旋操作（revolveR）

以目标节点为中心，将其左孩子提升为新的父节点，原目标节点变为左孩子的右子节点。

// 右旋操作：以parent为中心，顺时针旋转
void revolveR(Node* parent) {
    Node* subl = parent->_left;    // 旋转轴：parent的左孩子（新父节点）
    Node* sublr = subl->_right;    // subl的右子树（需重新挂载到parent）
    Node* grandparent = parent->_parent; // parent的父节点（用于上层连接）

    // 1. 将subl的右子树挂载到parent的左子树
    parent->_left = sublr;
    if (sublr != nullptr) {
        sublr->_parent = parent; // 维护子树的父指针
    }

    // 2. 核心旋转：将parent挂载到subl的右子树
    subl->_right = parent;
    parent->_parent = subl;

    // 3. 处理与上层节点（祖父）的连接
    if (grandparent == nullptr) {
        _root = subl; // 若parent是根节点，subl成为新根
        subl->_parent = nullptr;
    } else {
        // 根据parent在祖父节点的位置，挂载subl
        if (grandparent->_left == parent) {
            grandparent->_left = subl;
        } else {
            grandparent->_right = subl;
        }
        subl->_parent = grandparent; // 维护subl的父指针
    }
}

左旋操作（revolveL）

以目标节点为中心，将其右孩子提升为新的父节点，原目标节点变为右孩子的左子节点。

// 左旋操作：以parent为中心，逆时针旋转
void revolveL(Node* parent) {
    Node* subr = parent->_right;   // 旋转轴：parent的右孩子（新父节点）
    Node* subrl = subr->_left;     // subr的左子树（需重新挂载到parent）
    Node* grandparent = parent->_parent; // parent的父节点（用于上层连接）

    // 1. 将subr的左子树挂载到parent的右子树
    parent->_right = subrl;
    if (subrl != nullptr) {
        subrl->_parent = parent; // 维护子树的父指针
    }

    // 2. 核心旋转：将parent挂载到subr的左子树
    subr->_left = parent;
    parent->_parent = subr;

    // 3. 处理与上层节点（祖父）的连接
    if (grandparent == nullptr) {
        _root = subr; // 若parent是根节点，subr成为新根
        subr->_parent = nullptr;
    } else {
        // 根据parent在祖父节点的位置，挂载subr
        if (grandparent->_left == parent) {
            grandparent->_left = subr;
        } else {
            grandparent->_right = subr;
        }
        subr->_parent = grandparent; // 维护subr的父指针
    }
}

四、红黑树的辅助操作

除核心插入操作外，红黑树还需实现中序遍历、节点计数、高度计算、平衡校验等辅助功能。

4.1 中序遍历（验证 BST 特性）

红黑树作为 BST，其中序遍历结果为升序序列，可直接用于验证树的键值是否符合 "左小右大" 规则。

// 对外接口：中序遍历（升序输出键值对）
void inorder() {
    _inorder(_root);
    cout << endl;
}

// 私有递归实现：左→根→右
void _inorder(Node* root) {
    if (root == nullptr) return;
    _inorder(root->_left);  // 遍历左子树
    // 输出键值对及节点颜色（便于调试）
    cout << "(" << root->_kv.first << ":" << root->_kv.second 
         << "," << (root->_colour == RED ? "红" : "黑") << ") ";
    _inorder(root->_right); // 遍历右子树
}

4.2 节点总数统计

通过递归计算树的总节点数，反映红黑树存储的数据量。

// 对外接口：获取节点总数
int size() {
    return _size(_root);
}

// 私有递归实现：空树返回0，非空树=左子树数+右子树数+1
int _size(Node* root) {
    return (root == nullptr) ? 0 : (_size(root->_left) + _size(root->_right) + 1);
}

4.3 树的高度计算

树的高度是衡量红黑树平衡程度的直观指标。

// 对外接口：获取树的高度（根节点高度为1）
int height() {
    return _height(_root);
}

// 私有递归实现：空树高度为0，非空树高度=max(左高, 右高)+1
int _height(Node* root) {
    if (root == nullptr) return 0;
    int left_h = _height(root->_left);
    int right_h = _height(root->_right);
    return left_h > right_h ? left_h + 1 : right_h + 1;
}

4.4 红黑树规则校验

验证树是否满足红黑树的 5 条核心规则，确保实现正确性。

// 对外接口：校验是否为合法红黑树
bool isRBTree() {
    if (_root == nullptr) return true; // 空树是合法红黑树
    
    // 规则2：根节点必须为黑色
    if (_root->_colour != BLACK) {
        cout << "违反规则2：根节点不是黑色" << endl;
        return false;
    }
    
    // 计算基准黑高（从根到任意叶子的黑节点数量）
    int benchmark_black_count = 0;
    Node* cur = _root;
    while (cur) {
        if (cur->_colour == BLACK) {
            benchmark_black_count++;
        }
        cur = cur->_left; // 任意选择一条路径计算基准黑高
    }
    
    // 递归校验所有规则
    return _checkRules(_root, 0, benchmark_black_count);
}

// 私有递归校验实现
bool _checkRules(Node* root, int current_black_count, int benchmark_black_count) {
    if (root == nullptr) {
        // 规则3：空节点视为黑色，检查黑高是否一致
        if (current_black_count != benchmark_black_count) {
            cout << "违反规则5：黑高不一致" << endl;
            return false;
        }
        return true;
    }
    
    // 累加当前路径的黑节点数量
    if (root->_colour == BLACK) {
        current_black_count++;
    }
    
    // 规则4：红色节点的子节点必须为黑色
    if (root->_colour == RED) {
        if ((root->_left && root->_left->_colour == RED) || 
            (root->_right && root->_right->_colour == RED)) {
            cout << "违反规则4：存在连续红色节点" << endl;
            return false;
        }
    }
    
    // 递归校验左右子树
    return _checkRules(root->_left, current_black_count, benchmark_black_count) &&
           _checkRules(root->_right, current_black_count, benchmark_black_count);
}

五、完整 C++ 代码与使用示例

#pragma once
#include <iostream>
#include <utility>  // 用于std::pair
using namespace std;

// 定义节点颜色枚举：红黑树中节点只有只能是红色或黑色
enum Colour
{
    BLACK,  // 黑色节点
    RED     // 红色节点
};

// 红黑树节点结构模板
template<class k, class v>
struct RBTreeNode
{
    pair<k, v> _kv;                  // 存储键值对（k为键，v为值）
    Colour _colour;                  // 节点颜色
    RBTreeNode<k, v>* _left;         // 左子节点指针
    RBTreeNode<k, v>* _right;        // 右子节点指针
    RBTreeNode<k, v>* _parent;       // 父节点指针（红黑树需要父指针进行旋转和平衡调整）

    // 构造函数：初始化节点，新节点默认为红色（减少平衡调整次数）
    // 参数使用const引用避免拷贝，提高效率
    /*RBTreeNode    为什么新节点默认红色？
        红黑树性质：红色节点的子节点必须是黑色。若新节点为黑色，
        会导致所有包含该节点的路径黑高 + 1，破坏"所有路径黑高相等"的性质，
        调整成本更高；而红色节点仅可能导致连续红节点（可通过少量操作修复）
        * /
        RBTreeNode    为什么新节点默认红色？
        红黑树性质：红色节点的子节点必须是黑色。若新节点为黑色，
        会导致所有包含该节点的路径黑高 + 1，破坏"所有路径黑高相等"的性质，
        调整成本更高；而红色节点仅可能导致连续红节点（可通过少量操作修复）
        * /*/
        RBTreeNode(const pair<k, v>&kv)
        : _kv(kv)
        , _colour(RED)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
    {
    }
};

// 红黑树类模板
template<class k, class v>
class RBTree
{
    // 类型重定义，简化代码书写
    typedef RBTreeNode<k, v> Node;
public:
    // 插入键值对：返回是否插入成功（键已存在时返回false）
    bool insert(const pair<k, v>& kv)
    {
        // 情况1：树为空，直接创建根节点
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_colour = BLACK;  // 根节点必须为黑色（红黑树性质2）
            return true;
        }

        // 情况2：树非空，查找插入位置
        Node* parent = nullptr;  // 记录父节点
        Node* cur = _root;       // 遍历指针

        // 按key查找插入位置（二叉搜索树性质：左小右大）
        while (cur)
        {
            if (cur->_kv.first > kv.first)  // 当前节点key大于插入key，向左子树查找
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_kv.first < kv.first)  // 当前节点key小于插入key，向右子树查找
            {
                parent = cur;
                cur = cur->_right;
            }
            else  // key已存在，插入失败（红黑树不允许重复key）
            {
                return false;
            }
        }

        // 创建新节点并插入到树中
        cur = new Node(kv);
        cur->_parent = parent;  // 设置父指针

        // 根据key大小决定插入到父节点的左/右
        if (parent->_kv.first > kv.first)
        {
            parent->_left = cur;  // 插入到左子树
        }
        else
        {
            parent->_right = cur;  // 插入到右子树
        }

        // 插入后平衡调整：仅当父节点为红色时需要调整
        // （父节点为黑色时，插入红色节点不破坏任何性质）
        while (parent && parent->_colour == RED)
        {
            // 父节点为红色，则祖父节点一定存在且为黑色
            // （原因：红黑树性质4：红色节点的父节点必须是黑色）
            Node* grandfather = parent->_parent;

            // 分两种大情况：父节点是祖父节点的左孩子 or 右孩子（对称逻辑）
            if (grandfather->_left == parent)
            {
                // 情况A：父节点是祖父的左孩子
                Node* uncle = grandfather->_right;  // 叔叔节点是祖父的右孩子

                // 子情况A1：叔叔节点存在且为红色
                if (uncle && uncle->_colour == RED)
                {
                    // 处理方式：变色
                    parent->_colour = BLACK;    // 父节点变黑
                    uncle->_colour = BLACK;     // 叔叔节点变黑
                    grandfather->_colour = RED;  // 祖父节点变红

                    // 向上调整：祖父节点变红后可能与它的父节点（曾祖父）形成连续红节点
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    // 子情况A2：叔叔节点不存在或为黑色（需要旋转+变色）
                    if (cur == parent->_left)
                    {
                        // 子情况A2.1：cur是父节点的左孩子（LL型）
                        // 处理方式：右旋祖父节点
                        revolveR(grandfather);
                        // 变色：父节点变黑，祖父节点变红
                        parent->_colour = BLACK;
                        grandfather->_colour = RED;
                    }
                    else
                    {
                        // 子情况A2.2：cur是父节点的右孩子（LR型）
                        // 处理方式：先左旋父节点，再右旋祖父节点
                        revolveL(parent);
                        revolveR(grandfather);
                        // 变色：cur节点变黑，祖父节点变红
                        cur->_colour = BLACK;
                        grandfather->_colour = RED;
                    }
                    break;  // 旋转后已平衡，退出循环
                }
            }
            else
            {
                // 情况B：父节点是祖父的右孩子（与情况A对称）
                Node* uncle = grandfather->_left;  // 叔叔节点是祖父的左孩子

                // 子情况B1：叔叔节点存在且为红色
                if (uncle && uncle->_colour == RED)
                {
                    // 处理方式：变色（与A1对称）
                    parent->_colour = BLACK;
                    uncle->_colour = BLACK;
                    grandfather->_colour = RED;

                    // 向上调整
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    // 子情况B2：叔叔节点不存在或为黑色（需要旋转+变色）
                    if (cur == parent->_right)
                    {
                        // 子情况B2.1：cur是父节点的右孩子（RR型）
                        // 处理方式：左旋祖父节点
                        revolveL(grandfather);
                        // 变色：父节点变黑，祖父节点变红
                        parent->_colour = BLACK;
                        grandfather->_colour = RED;
                    }
                    else
                    {
                        // 子情况B2.2：cur是父节点的左孩子（RL型）
                        // 处理方式：先右旋父节点，再左旋祖父节点
                        revolveR(parent);
                        revolveL(grandfather);
                        // 变色：cur节点变黑，祖父节点变红
                        cur->_colour = BLACK;
                        grandfather->_colour = RED;
                    }
                    break;  // 旋转后已平衡，退出循环
                }
            }
        }

        // 最终确保根节点为黑色（平衡调整可能导致根节点变色）
        _root->_colour = BLACK;
        return true;
    }

    // 中序遍历：按key升序输出（验证二叉搜索树性质）
    void inorder()
    {
        _inorder(_root);  // 调用私有递归函数
        cout << endl;
    }

    // 平衡检查：验证红黑树的所有性质
    bool isbalaence()
    {
        // 空树视为平衡
        if (_root == nullptr)
            return true;

        // 性质2：根节点必须为黑色
        if (_root->_colour == RED)
        {
            cout << "平衡检查失败：根节点为红色" << endl;
            return false;
        }

        // 计算基准黑高（从根到最左路径的黑色节点数）
        int base_black_count = 0;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_colour == BLACK)
                base_black_count++;
            cur = cur->_left;
        }

        // 递归检查所有路径的黑高和连续红节点
        return _check_balance(_root, 0, base_black_count);
    }

    // 获取树的节点总数
    int size()
    {
        return _size(_root);  // 调用私有递归函数
    }

    // 获取树的高度（最大深度）
    int height()
    {
        return _height(_root);  // 调用私有递归函数
    }

    // 按key查找节点（返回节点指针，未找到返回nullptr）
    Node* find(const pair<k, v>& kv)
    {
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first > kv.first)  // 当前key大，向左找
            {
                cur = cur->_left;
            }
            else if (cur->_kv.first < kv.first)  // 当前key小，向右找
            {
                cur = cur->_right;
            }
            else  // 找到匹配key
            {
                return cur;
            }
        }
        return nullptr;  // 未找到
    }

private:
    // 递归计算树的高度
    int _height(Node* root)
    {
        if (root == nullptr)
            return 0;  // 空节点高度为0
        int left_h = _height(root->_left);   // 左子树高度
        int right_h = _height(root->_right); // 右子树高度
        return max(left_h, right_h) + 1;     // 当前节点高度= max(左右子树高度)+1
    }

    // 递归计算节点总数
    int _size(Node* root)
    {
        if (root == nullptr)
            return 0;  // 空节点计数为0
        // 当前节点数=1（自身）+左子树节点数+右子树节点数
        return 1 + _size(root->_left) + _size(root->_right);
    }

    // 递归平衡检查：验证两个核心性质
    // 参数：当前节点、当前路径黑节点数、基准黑高（最左路径的黑节点数）
    bool _check_balance(Node* cur, int black_count, int base_black_count)
    {
        // 空节点：检查当前路径黑高是否与基准一致
        if (cur == nullptr)
        {
            if (black_count != base_black_count)
            {
                cout << "平衡检查失败：黑高不一致" << endl;
                return false;
            }
            return true;
        }

        // 累计黑色节点数
        if (cur->_colour == BLACK)
            black_count++;

        // 检查性质4：是否存在连续红色节点
        if (cur->_colour == RED && cur->_parent->_colour == RED)
        {
            cout << "平衡检查失败：存在连续红色节点" << endl;
            return false;
        }

        // 递归检查左右子树
        return _check_balance(cur->_left, black_count, base_black_count) &&
            _check_balance(cur->_right, black_count, base_black_count);
    }

    // 递归中序遍历实现
    void _inorder(Node* root)
    {
        if (root == nullptr)
            return;  // 空节点直接返回
        _inorder(root->_left);  // 遍历左子树
        // 输出当前节点信息（键、值）
        cout << root->_kv.first << ' ' << root->_kv.second << ' ' << endl;
        _inorder(root->_right); // 遍历右子树
    }

    // 左旋操作：以parent的右孩子为轴进行逆时针旋转
    void revolveL(Node* parent)
    {
        Node* subr = parent->_right;  // subr是旋转轴（parent的右孩子）
        Node* subrl = subr->_left;    // subr的左子树

        // 步骤1：将subr的左子树连接到parent的右子树
        if (subrl)  // 若subrl存在，更新其父指针
            subrl->_parent = parent;
        parent->_right = subrl;       // parent的右指针指向subrl

        // 步骤2：记录parent的父节点（用于后续连接）
        Node* parentparent = parent->_parent;

        // 步骤3：核心旋转：subr成为parent的父节点
        subr->_left = parent;  // subr的左指针指向parent
        parent->_parent = subr; // parent的父指针指向subr

        // 步骤4：处理与上层节点的连接
        if (parent == _root)  // 若parent是根节点
        {
            _root = subr;      // 更新根节点为subr
            subr->_parent = nullptr;  // 新根的父指针为空
        }
        else  // parent不是根节点
        {
            // 根据parent在parentparent中的位置，连接subr
            if (parentparent->_left == parent)
                parentparent->_left = subr;
            else
                parentparent->_right = subr;
            subr->_parent = parentparent;  // subr的父指针指向parentparent
        }
    }

    // 右旋操作：以parent的左孩子为轴进行顺时针旋转
    void revolveR(Node* parent)
    {
        Node* subl = parent->_left;   // subl是旋转轴（parent的左孩子）
        Node* sublr = subl->_right;   // subl的右子树

        // 步骤1：将subl的右子树连接到parent的左子树
        if (sublr)  // 若sublr存在，更新其父指针
            sublr->_parent = parent;
        parent->_left = sublr;        // parent的左指针指向sublr

        // 步骤2：记录parent的父节点（用于后续连接）
        Node* parentparent = parent->_parent;

        // 步骤3：核心旋转：subl成为parent的父节点
        subl->_right = parent;  // subl的右指针指向parent
        parent->_parent = subl; // parent的父指针指向subl

        // 步骤4：处理与上层节点的连接
        if (parent == _root)  // 若parent是根节点
        {
            _root = subl;      // 更新根节点为subl
            subl->_parent = nullptr;  // 新根的父指针为空
        }
        else  // parent不是根节点
        {
            // 根据parent在parentparent中的位置，连接subl
            if (parentparent->_left == parent)
                parentparent->_left = subl;
            else
                parentparent->_right = subl;
            subl->_parent = parentparent;  // subl的父指针指向parentparent
        }
    }

private:
    Node* _root = nullptr;  // 根节点指针（初始为空）
};

5.2 使用示例

#include "RBTree.h"
#include <iostream>
using namespace std;

int main() {
    // 创建红黑树，键为int，值为string
    RBTree<int, string> rbt;

    // 插入键值对（包含有序数据，测试平衡维护）
    rbt.insert({3, "a"});
    rbt.insert({2, "b"});
    rbt.insert({1, "c"}); // 触发LL型失衡，右旋修复
    rbt.insert({4, "d"});
    rbt.insert({5, "e"}); // 触发RR型失衡，左旋修复
    rbt.insert({6, "f"});
    rbt.insert({7, "g"});
    rbt.insert({10, "h"});
    rbt.insert({9, "i"});
    rbt.insert({8, "j"}); // 触发RL型失衡，先右旋后左旋修复

    // 中序遍历（应输出升序键值对及颜色）
    cout << "中序遍历结果：";
    rbt.inorder();

    // 输出树的基本信息
    cout << "节点总数：" << rbt.size() << endl;
    cout << "树的高度：" << rbt.height() << endl;
    cout << "是否为合法红黑树：" << (rbt.isRBTree() ? "是" : "否") << endl;

    return 0;
}

输出结果：

plaintext

中序遍历结果：(1:c,黑) (2:b,黑) (3:a,红) (4:d,黑) (5:e,红) (6:f,黑) (7:g,红) (8:j,黑) (9:i,红) (10:h,黑) 
节点总数：10
树的高度：5
是否为合法红黑树：是

六、红黑树的优缺点与适用场景

优点

1. 高效稳定：插入、查找、删除的时间复杂度均为 O (logn)，实际性能优于 AVL 树；
2. 旋转操作少：插入时最多只需 2 次旋转，删除时最多只需 3 次旋转，维护成本低；
3. 空间开销小：仅需一个额外的颜色位存储节点状态，空间效率高。

缺点

1. 实现复杂：平衡维护逻辑涉及多种场景判断，代码实现难度高于 AVL 树；
2. 理论复杂：5 条规则的相互约束和黑高计算增加了理解难度。

适用场景

• 频繁插入删除的场景（如 STL 中的 map/set、Linux 内核调度）；
• 对旋转操作开销敏感，允许一定高度差的场景；
• 需要稳定 O (logn) 性能的工业级应用（如数据库索引、缓存系统）。

红黑树的精髓在于通过 "颜色规则" 实现近似平衡，在保持 BST 高效查找特性的同时，大幅降低了平衡维护的成本。相比 AVL 树的 "严格平衡"，红黑树的 "近似平衡" 在实际应用中往往更具优势，这也是它成为工业界首选平衡树的核心原因。建议结合代码示例调试不同插入场景，观察颜色变化和旋转过程，加深对红黑树平衡机制的理解。