RBT红黑树——数据结构系列教程(c++版)

#ifndef ENTITYS_H_INCLUDED
#define ENTITYS_H_INCLUDED

//************************************************************************************************************************************************************************
//                                                                      自定义类型
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//                                                                    学生结构体(Student)
//========================================================================================================================================================================
struct Student {
    int id;// 学号
    std::string name;// 姓名
    std::string dob;// 出生日期
    std::string sex;// 性别
    std::string gender;// 民族
    std::string address;// 地址
    float score;// 入学总分
    std::string school;// 学校
    std::string team;// 班级
    std::string status;// 状态

    bool operator<(const Student& other) const { return id < other.id; }
    bool operator>(const Student& other) const { return id > other.id; }
    bool operator==(const Student& other) const { return id == other.id; }
    bool operator!=(const Student& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        os << "[" << s.id<< ", " << s.name << ", " << s.dob << ", " << s.sex << ", " << s.gender  << ", " << s.address << ", " << s.score<< ", " << s.school<< ", " << s.team<< ", " << s.status << "]";
        return os;
    }
};

//========================================================================================================================================================================
//
//                                                                    学生索引结构体(Student)
//
//========================================================================================================================================================================
struct StudentIndex {
    int id;// 学号
    int row;// 行号

    bool operator<(const StudentIndex& other) const { return id < other.id; }
    bool operator>(const StudentIndex& other) const { return id > other.id; }
    bool operator==(const StudentIndex& other) const { return id == other.id; }
    bool operator!=(const StudentIndex& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const StudentIndex& i) {
        os << "[" << i.id << ", " << i.row<< "]";
        return os;
    }
};

//========================================================================================================================================================================
//                                                                    迷宫坐标结构体(Pos)
//========================================================================================================================================================================
struct Pos{
    int x;     //x坐标
    int y;    //y坐标
    int step; //步数
};

//========================================================================================================================================================================
//                                                                    打印任务结构体(PrintTask)
//========================================================================================================================================================================
struct PrintTask{
    int taskId;     // 任务ID
    char content[50]; // 打印内容
};

#endif // ENTITYS_H_INCLUDED
        

#ifndef LINKEDRBTREE_H_INCLUDED
#define LINKEDRBTREE_H_INCLUDED

#include <iostream>
#include <string>
#include "Entitys.h"

// 颜色枚举
typedef enum { RED, BLACK } Color;

// 红黑树节点结构体
template <typename T>
struct RBTNode {
    T data;
    Color color;
    RBTNode* left;
    RBTNode* right;
    RBTNode* parent;

    // 构造函数
    RBTNode(const T& val, Color c = RED) 
        : data(val), color(c), left(nullptr), right(nullptr), parent(nullptr) {}
};

// 红黑树结构体
template <typename T>
struct LinkedRBTree {
private:
    RBTNode<T>* root;
    RBTNode<T>* NIL;  // 虚拟叶子节点

    // 私有辅助函数
    RBTNode<T>* createNode(const T& val);                 // 创建新节点
    RBTNode<T>* findMin(RBTNode<T>* node);          // 找最小值节点（后继节点）
    RBTNode<T>* findMax(RBTNode<T>* node);          // 找最大值节点（后继节点）
    void leftRotate(RBTNode<T>* x);                       // 右旋转
    void rightRotate(RBTNode<T>* x);                      // 左旋转
    void transplant(RBTNode<T>* u, RBTNode<T>* v);  // 节点替换
    void insertFixup(RBTNode<T>* z);                      // 插入后修复红黑树性质
    void deleteFixup(RBTNode<T>* x);                      // 删除后修复红黑树性质   
    bool searchNode(RBTNode<T>* node, const T& val);      // 查找节点（模板类型）
    void preOrder(RBTNode<T>* node);                      // 前序遍历（根 → 左 → 右）
    void inOrder(RBTNode<T>* node);                       // 中序遍历（左 → 根 → 右）→ 升序输出
    void postOrder(RBTNode<T>* node);                     // 后序遍历（左 → 右 → 根）
    void destroyTree(RBTNode<T>* node);                   // 销毁整棵树（防止内存泄漏）

public:
    // 构造函数
    LinkedRBTree() : root(nullptr) {
        NIL = new RBTNode<T>(T{}, Color::BLACK);
        root = NIL;
    }

    // 对外接口
    int isEmpty();                    // 判断树是否为空
    void insertNode(const T& val);  // 插入节点
    void deleteNode(const T& val);  // 删除节点
    bool searchNode(const T& val);  // 查找节点
    void preOrder();                // 前序遍历
    void inOrder();                 // 中序遍历
    void postOrder();               // 后序遍历
    void destroyTree();

    // 析构函数：自动销毁树，避免内存泄漏
    ~LinkedRBTree() {
        destroyTree();
        delete NIL;
    }
};

#endif // LINKEDRBTREE_H_INCLUDED

5.3 LinkedRBTree.cpp 程序代码

#include "LinkedRBTree.h"
//=================================================================================================
// 私有函数实现
//=================================================================================================

//创建新节点
template <typename T>
RBTNode<T>* LinkedRBTree<T>::createNode(const T& val) {
    RBTNode<T>* node = new RBTNode<T>(val);
    node->left = NIL;
    node->right = NIL;
    node->parent = NIL;
    node->color = RED;
    return node;
}

// 找最小值节点（后继节点）
template <typename T>
RBTNode<T>* LinkedRBTree<T>::findMin(RBTNode<T>* node) {
    if (node == NIL) return NIL;
    while (node->left != NIL) {
        node = node->left;
    }
    return node;
}

// 找最大值节点（后继节点）
template <typename T>
RBTNode<T>* LinkedRBTree<T>::findMax(RBTNode<T>* node) {
    if (node == NIL) return NIL;
    while (node->right != NIL) {
        node = node->right;
    }
    return node;
}

// 左旋
template <typename T>
void LinkedRBTree<T>::leftRotate(RBTNode<T>* x) {
    RBTNode<T>* y = x->right;
    x->right = y->left;

    if (y->left != NIL) {
        y->left->parent = x;
    }

    y->parent = x->parent;
    if (x->parent == NIL) {
        root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }

    y->left = x;
    x->parent = y;
}

// 右旋
template <typename T>
void LinkedRBTree<T>::rightRotate(RBTNode<T>* x) {
    RBTNode<T>* y = x->left;
    x->left = y->right;

    if (y->right != NIL) {
        y->right->parent = x;
    }

    y->parent = x->parent;
    if (x->parent == NIL) {
        root = y;
    } else if (x == x->parent->right) {
        x->parent->right = y;
    } else {
        x->parent->left = y;
    }

    y->right = x;
    x->parent = y;
}

// 节点替换
template <typename T>
void LinkedRBTree<T>::transplant(RBTNode<T>* u, RBTNode<T>* v) {
    if (u->parent == NIL) {
        root = v;
    } else if (u == u->parent->left) {
        u->parent->left = v;
    } else {
        u->parent->right = v;
    }
    v->parent = u->parent;
}

// 插入修复
template <typename T>
void LinkedRBTree<T>::insertFixup(RBTNode<T>* z) {
    // 循环修复：直到父节点为黑色或z成为根
    while (z->parent->color == Color::RED ) {
        if (z->parent == z->parent->parent->left) { // 父节点是祖父的左子
            RBTNode<T>* u = z->parent->parent->right;     // 叔父节点（祖父的右子）

            // 子场景2.1：叔父是红色 → 重着色+递归向上
            if (u->color == Color::RED) {
                z->parent->color = Color::BLACK;    // 父节点改黑
                u->color = Color::BLACK;            // 叔父改黑
                z->parent->parent->color = Color::RED; // 祖父改红
                z = z->parent->parent;              // 递归处理祖父
            } else { // 子场景2.2：叔父是黑色
                // 子场景2.2.2：折线（左右）→ 先左旋转直线
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(z);
                }
                // 子场景2.2.1：直线（左左）→ 右旋+颜色交换
                z->parent->color = Color::BLACK;
                z->parent->parent->color = Color::RED;
                rightRotate(z->parent->parent);
            }
        } else { // 父节点是祖父的右子（对称逻辑）
            RBTNode<T>* u = z->parent->parent->left;

            if (u->color == Color::RED) {
                z->parent->color = Color::BLACK;
                u->color = Color::BLACK;
                z->parent->parent->color = Color::RED;
                z = z->parent->parent;
            } else {
                // 子场景2.2.2：折线（右左）→ 先右旋转直线
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(z);
                }
                // 子场景2.2.1：直线（右右）→ 左旋+颜色交换
                z->parent->color = Color::BLACK;
                z->parent->parent->color = Color::RED;
                leftRotate(z->parent->parent);
            }
        }
    }
    // 强制根节点为黑色（修复场景0）
    root->color = Color::BLACK;
}

// 删除修复
template <typename T>
void LinkedRBTree<T>::deleteFixup(RBTNode<T>* x) {
    // 循环修复：直到x是根 或 x变为红色（红节点不影响黑高）
    while (x != root && x->color == Color::BLACK) {
        if (x == x->parent->left) {  // x是左子（主场景）
            RBTNode<T>* w = x->parent->right;   // w是x的兄弟节点

            // ========== 场景1：w是红色 ==========
            // 特征：w红 → 父节点必黑（无连续红节点）
            // 操作：w改黑、父改红 + 左旋父节点
            // 目标：将w转为黑色，转为场景3/4/5
            if (w->color == Color::RED) {
                w->color = Color::BLACK;
                x->parent->color = Color::RED;
                leftRotate(x->parent);
                w = x->parent->right;
            }

            // ========== 场景2：w黑，w的两个子均黑 ==========
            // 特征：无红节点可借，黑高仍失衡
            // 操作：w改红，x上移为父节点
            // 目标：向上传递黑高失衡问题
            if (w->left->color == Color::BLACK && w->right->color == Color::BLACK) {
                w->color = Color::RED;
                x = x->parent;
            } else {
                // ========== 场景3：w是黑色，w左子红、右子黑 ==========
                // 特征：折线型红节点，无法直接借
                // 操作：w左子改黑、w改红 + 右旋w
                // 目标：旋转转为直线型（场景4）
                if (w->right->color == Color::BLACK) {
                    w->left->color = Color::BLACK;
                    w->color = Color::RED;
                    rightRotate(w);
                    w = x->parent->right;
                }
                // ========== 场景4：w是黑色，w右子红 ==========
                // 特征：直线型红节点，可借红节点补黑高
                // 操作：w继承父颜色、父改黑、w右子改黑 + 左旋父节点
                // 目标：重着色+旋转，终止修复
                w->color = x->parent->color;
                x->parent->color = Color::BLACK;
                w->right->color = Color::BLACK;
                leftRotate(x->parent);
                x = root;  // 终止循环
            }
        } else {  // x是右子（对称逻辑）
            RBTNode<T>* w = x->parent->left;

            if (w->color == Color::RED) {
                w->color = Color::BLACK;
                x->parent->color = Color::RED;
                rightRotate(x->parent);
                w = x->parent->left;
            }

            if (w->right->color == Color::BLACK && w->left->color == Color::BLACK) {
                w->color = Color::RED;
                x = x->parent;
            } else {
                if (w->left->color == Color::BLACK) {
                    w->right->color = Color::BLACK;
                    w->color = Color::RED;
                    leftRotate(w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = Color::BLACK;
                w->left->color = Color::BLACK;
                rightRotate(x->parent);
                x = root;
            }
        }
    }
    // 最终修复：若x是根 或 x变为红色，强制设为黑色（保证根为黑）
    x->color = Color::BLACK;
}

// 查找节点（模板类型）
template <typename T>
bool LinkedRBTree<T>::searchNode(RBTNode<T>* node, const T& val) {
    if (node == NIL) return false;
    if (val == node->data) return true;
    return val < node->data ? searchNode(node->left, val) : searchNode(node->right, val);
}

// 前序遍历（根 → 左 → 右）
template <typename T>
void LinkedRBTree<T>::preOrder(RBTNode<T>* node) {
    if (node == NIL) return;
    std::cout << "Data: " << node->data << ", Color: " << (node->color == RED ? "RED" : "BLACK") << ", My : " << node << ", Parent : " << node->parent << std::endl;
    preOrder(node->left);
    preOrder(node->right);
}

// 中序遍历（左 → 根 → 右）→ 升序输出
template <typename T>
void LinkedRBTree<T>::inOrder(RBTNode<T>* node) {
    if (node == NIL) return;
    inOrder(node->left);
    std::cout << "Data: " << node->data << ", Color: " << (node->color == RED ? "RED" : "BLACK") << ", My : " << node << ", Parent : " << node->parent << std::endl;
    inOrder(node->right);
}

// 后序遍历（左 → 右 → 根)
template <typename T>
void LinkedRBTree<T>::postOrder(RBTNode<T>* node) {
    if (node == NIL) return;
    postOrder(node->left);
    postOrder(node->right);
    std::cout << "Data: " << node->data << ", Color: " << (node->color == RED ? "RED" : "BLACK") << ", My : " << node << ", Parent : " << node->parent << std::endl;
}

// 销毁整棵树（防止内存泄漏）
template <typename T>
void LinkedRBTree<T>::destroyTree(RBTNode<T>* node) {
    if (node == NIL) return;
    destroyTree(node->left);
    destroyTree(node->right);
    delete node;
}

//=================================================================================================
// 公共函数实现
//=================================================================================================

// 判断树是否为空
template <typename T>
    int LinkedRBTree<T>::isEmpty() {
        return (root == NIL) ? 1 : 0;
}

// 迭代式插入节点
template <typename T>
void LinkedRBTree<T>::insertNode(const T& val) {
    // 1. 检查重复值（提前遍历）
    RBTNode<T>* curr = root;
    RBTNode<T>* parent = NIL;

    // 迭代查找插入位置
    while (curr != NIL) {
        parent = curr;
        if (val == curr->data) {
            std::cout << "Warning: " << val << " already exists!" << std::endl;
            return; // 重复值，直接返回
        } else if (val < curr->data) {
            curr = curr->left;
        } else {
            curr = curr->right;
        }
    }

    // 2. 创建新节点
    RBTNode<T>* z = createNode(val);
    z->parent = parent;

    // 3. 插入节点到树中
    if (parent == NIL) {
        root = z; // 空树，新节点作为根
        root->color = BLACK; // 根节点强制为黑
        return;
    } else if (val < parent->data) {
        parent->left = z;
    } else {
        parent->right = z;
    }

    // 插入修复前校验z的合法性
    if (z == NIL || z == nullptr) {
        return;
    }
    // 4. 修复红黑树性质
    insertFixup(z);
}

// 删除函数
template <typename T>
void LinkedRBTree<T>::deleteNode(const T& val) {
    // 1. 查找待删除节点z
    RBTNode<T>* z = root;
    while (z != NIL && z->data != val) {
        if (val < z->data)
            z = z->left;
        else
            z = z->right;
    }
    if (z == NIL) {
        std::cout << "节点" << val << "不存在！" << std::endl;
        return;
    }

    // 2. 替换待删除节点z
    RBTNode<T>* y = nullptr;   //z的代替者
    RBTNode<T>* x = nullptr;   //y的代替者
    Color yOriginalColor;       //y原来的颜色

    // 情况1：z无左子，用右子替代z的位置
    if (z->left == NIL) {
        yOriginalColor = z->right->color;  // 记录y的原始颜色
        x = z->right;                      // 记录y的原始位置
        z->right->color = z->color;        // 将y的颜色设置成z的颜色(y的颜色丢失)。
        transplant(z, z->right);           // 将z->right转移至z的位置，让z从树中分离
    }
    // 情况2：z无右子，用左子替代z的位置
    else if (z->right == NIL) {
        yOriginalColor = z->left->color;    // 记录y的原始颜色
        x = z->left;                        // 记录y的原始位置
        z->left->color = z->color;          // 将y的颜色设置成z的颜色(y的颜色丢失)。
        transplant(z, z->left);             //将z->left转移至z的位置，让z从树中分离
    }
    // 情况3：z有左右子 → 找到z的后继节点y（右子树最小值节点或者左子树最大值节点），用y替代z,用x替代y(x->y->z)。
    else {
        // a. 找后继
        y = findMin(z->right);      // 找后继，右子树最小值节点
        //y = findMax(z->left);     // 找后继，左子树最大值节点
        yOriginalColor = y->color;  // 记录y的原始颜色
        x = y->right;               // 记录y的原始位置

        // b. 将y->right转移至y的位置，让y从树中分离
        transplant(y, y->right);

        // c. 将z的右子树转移至y的右子树
        y->right = z->right;        //将z->right转移至y->right
        y->right->parent = y;       //将z->right父亲指针指向y，至此z的右子成功转移至y的右子树

        // d. 将y移动至z的位置，让z从树中分离
        transplant(z, y);

        //e. 将z的左子树转转移到y的左子树
        y->left = z->left;      //将z->left转移至y->left
        y->left->parent = y;    //将z->left父亲指针指向y,至此z的左子成功转移至y的左子
        y->color = z->color;    //将y的颜色设置成z的颜色(y的颜色丢失)，至此y成功替换掉z。
    }

    //替换后，y的颜色丢失，若丢失是红色，则不做任何操作，红黑树的任何属性都不会被破坏；
    //若丢失是黑色的，显然它所在的路径上就少一个黑色结点，红黑树的性质就被破坏了，这时执行一个 deleteFixup（x）从y的替代者y->right(x)处开始修补这棵树。
    if (yOriginalColor == Color::BLACK) {

        deleteFixup(x);
    }

    // 3. 删除节点z
    delete z;
}

// 查找节点
template <typename T>
bool LinkedRBTree<T>::searchNode(const T& val) {
    return searchNode(root, val);
}

// 前序遍历（对外接口）
template <typename T>
void LinkedRBTree<T>::preOrder() {
    if (isEmpty()) {
        std::cout << "Tree empty!" << std::endl;
        return;
    }
    std::cout << "===== Pre-Order =====" << std::endl;
    preOrder(root);
    std::cout << "=====================" << std::endl;
}

// 中序遍历（对外接口）
template <typename T>
void LinkedRBTree<T>::inOrder() {
    if (isEmpty()) {
        std::cout << "Tree empty!" << std::endl;
        return;
    }
    std::cout << "===== In-Order =====" << std::endl;
    inOrder(root);
    std::cout << "====================" << std::endl;
}

// 后序遍历（对外接口）
template <typename T>
void LinkedRBTree<T>::postOrder() {
    if (isEmpty()) {
        std::cout << "Tree empty!" << std::endl;
        return;
    }
    std::cout << "===== Post-Order =====" << std::endl;
    postOrder(root);
    std::cout << "======================" << std::endl;
}

// 销毁整棵树（防止内存泄漏）
template <typename T>
void LinkedRBTree<T>::destroyTree() {
    destroyTree(root);
    root = NIL;
}

// 显式实例化
template class LinkedRBTree<int>;
template class LinkedRBTree<char>;
template class LinkedRBTree<float>;
template class LinkedBSTree<std::string>;

5.4 main.cpp 测试代码

#include "LinkedRBTree.h"
#include <iostream>
#include <string>
#include "LinkedRBTree.h"

int main() {
    // ==================== 测试1：int类型红黑树 ====================
    LinkedRBTree<int> intTree;
    int intKeys[] = {10, 20, 30, 15, 25, 5, 8};
    int n = sizeof(intKeys)/sizeof(intKeys[0]);

    // 插入int节点
    std::cout << "=== Insert int keys: ";
    for (int i = 0; i < n; i++) {
        std::cout << intKeys[i] << " ";
        intTree.insertNode(intKeys[i]);
    }
    std::cout << "===" << std::endl;

    intTree.preOrder();

    // 查找测试
    int target = 31;
    if (intTree.searchNode(target)) {
        std::cout << "\nFound " << target << " in int tree!" << std::endl;
    }

    // 删除测试
    int deleteKey = 5;
    std::cout << "\n=== Delete key: " << deleteKey << " ===" << std::endl;
    intTree.deleteNode(deleteKey);
    // 前序遍历
    intTree.preOrder();

    // 销毁树（析构函数自动调用，此处显式调用演示）
    intTree.destroyTree();
    
    return 0;
}

六、注意事项与优化建议

5.1 注意事项

5.2 优化建议

• 迭代式遍历：将递归遍历改为迭代式，避免栈溢出（适合超大树）；
• 批量插入：先按BST插入所有节点，再统一调整平衡，减少修复次数；
• 性能统计：增加size()、getHeight()等接口，便于监控树的状态；
• 可视化：添加打印树结构的接口，便于调试。

七、总结

红黑树的核心是“牺牲严格平衡，降低调整代价”，通过颜色规则和旋转操作，保证树的高度始终在O(logn)级别。本教程基于链表实现的模板化红黑树代码，从原理到实战，覆盖了红黑树的核心操作与使用场景。掌握红黑树不仅能理解“自平衡”的设计思想，也能为后续学习STL容器打下基础。

你可以基于本教程的代码，尝试扩展功能（如批量删除、树的复制、序列化等），进一步加深对红黑树的理解。