红黑树：数据世界的平衡守护者

在 C++ 算法的神秘森林里，红黑树是一棵充满智慧的 “魔法树”。它既不像普通二叉搜索树那样容易失衡，也不像 AVL 树对平衡要求那么苛刻。作为 C++ 算法小白，今天就和大家一起深入探索红黑树的奥秘，看看它是如何成为数据世界的平衡守护者的！​

红黑树是什么？​

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。通过对树的节点颜色进行约束，红黑树确保了树在最坏情况下，依然能保持相对平衡，从而让搜索、插入和删除操作的时间复杂度稳定在 ​

O(logn)

。​

红黑树的规则​

1. 节点颜色：每个节点要么是红色，要么是黑色。​

1. 根节点：根节点是黑色。​

1. 叶子节点：每个叶子节点（NIL 节点，空节点）是黑色。​

1. 红色节点：如果一个节点是红色的，那么它的两个子节点都是黑色的。​

1. 路径黑色节点数：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。​

这五条规则就像是红黑树的 “生存法则”，让它始终保持着良好的平衡状态。可以把红黑树想象成一个严格遵守交通规则的城市，不同颜色的节点如同不同类型的车辆，在规则的约束下有序行驶，确保城市不会陷入混乱。​

红黑树的实现​

在 C++ 中，我们可以通过定义节点结构和相关操作来实现红黑树。以下是一个简化版的红黑树实现代码，并对关键部分进行详细解释。​

节点结构定义​

#include <iostream>

// 定义红黑树节点结构
struct RBNode {
    int key;
    bool color;  // true 表示红色，false 表示黑色
    RBNode* left;
    RBNode* right;
    RBNode* parent;

    RBNode(int k) : key(k), color(true), left(nullptr), right(nullptr), parent(nullptr) {}
};

每个节点包含键值 key 、颜色 color 、左右子节点指针 left 和 right ，以及父节点指针 parent 。节点默认颜色为红色，因为新插入节点为红色，在大多数情况下能减少调整操作。​

红黑树类定义与基本操作​

class RedBlackTree {
private:
    RBNode* root;

    // 左旋操作
    void leftRotate(RBNode* x) {
        RBNode* y = x->right;
        x->right = y->left;
        if (y->left != nullptr) {
            y->left->parent = x;
        }
        y->parent = x->parent;
        if (x->parent == nullptr) {
            root = y;
        } else if (x == x->parent->left) {
            x->parent->left = y;
        } else {
            x->parent->right = y;
        }
        y->left = x;
        x->parent = y;
    }

    // 右旋操作
    void rightRotate(RBNode* x) {
        RBNode* y = x->left;
        x->left = y->right;
        if (y->right != nullptr) {
            y->right->parent = x;
        }
        y->parent = x->parent;
        if (x->parent == nullptr) {
            root = y;
        } else if (x == x->parent->right) {
            x->parent->right = y;
        } else {
            x->parent->left = y;
        }
        y->right = x;
        x->parent = y;
    }

    // 插入节点后的修复操作
    void insertFixup(RBNode* z) {
        while (z != root && z->parent->color == true) {
            if (z->parent == z->parent->parent->left) {
                RBNode* y = z->parent->parent->right;
                if (y != nullptr && y->color == true) {
                    z->parent->color = false;
                    y->color = false;
                    z->parent->parent->color = true;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->right) {
                        z = z->parent;
                        leftRotate(z);
                    }
                    z->parent->color = false;
                    z->parent->parent->color = true;
                    rightRotate(z->parent->parent);
                }
            } else {
                RBNode* y = z->parent->parent->left;
                if (y != nullptr && y->color == true) {
                    z->parent->color = false;
                    y->color = false;
                    z->parent->parent->color = true;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        rightRotate(z);
                    }
                    z->parent->color = false;
                    z->parent->parent->color = true;
                    leftRotate(z->parent->parent);
                }
            }
        }
        root->color = false;
    }

public:
    RedBlackTree() : root(nullptr) {}

    // 插入节点
    void insert(int key) {
        RBNode* z = new RBNode(key);
        RBNode* y = nullptr;
        RBNode* x = root;

        while (x != nullptr) {
            y = x;
            if (z->key < x->key) {
                x = x->left;
            } else {
                x = x->right;
            }
        }

        z->parent = y;
        if (y == nullptr) {
            root = z;
        } else if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }

        insertFixup(z);
    }

    // 中序遍历
    void inorderTraversal(RBNode* node) {
        if (node != nullptr) {
            inorderTraversal(node->left);
            std::cout << node->key << " ";
            inorderTraversal(node->right);
        }
    }

    void inorderTraversal() {
        inorderTraversal(root);
        std::cout << std::endl;
    }
};

1. 旋转操作：左旋 leftRotate 和右旋 rightRotate 是红黑树保持平衡的重要手段。左旋以某个节点 x 为中心，将其右子节点 y 提升，x 变为 y 的左子节点；右旋则相反。就像在玩积木时，通过旋转积木块来调整结构，让树重新达到平衡。​

1. 插入修复操作：insertFixup 函数在插入新节点后，根据红黑树规则进行调整。如果新插入节点的父节点是红色，就可能违反规则，需要通过变色和旋转操作来修复，确保树满足所有红黑树规则。​

1. 插入节点：insert 函数先按照普通二叉搜索树的方式找到插入位置，插入新节点后调用 insertFixup 进行修复，维持红黑树的平衡。​

1. 中序遍历：inorderTraversal 函数用于遍历红黑树，按顺序输出节点的键值，方便查看树的结构和内容。​

例题讲解：使用红黑树实现动态数据集合管理​

问题描述​

假设我们需要管理一个动态的整数集合，要求能够快速插入新元素，并按顺序输出集合中的所有元素。使用红黑树来实现这个功能。​

代码示例​

int main() {
    RedBlackTree rbt;
    rbt.insert(5);
    rbt.insert(3);
    rbt.insert(7);
    rbt.insert(2);
    rbt.insert(4);
    rbt.insert(6);
    rbt.insert(8);

    std::cout << "Inorder traversal of the Red-Black Tree: ";
    rbt.inorderTraversal();

    return 0;
}

代码解释​

在 main 函数中，创建了一个红黑树对象 rbt ，然后依次插入多个整数。插入过程中，红黑树会自动调整结构，保持平衡。最后通过中序遍历，按顺序输出红黑树中的所有节点键值，得到有序的整数集合。​

红黑树在很多场景都有重要应用，比如 C++ 标准库中的 map 和 set ，底层实现就用到了红黑树。它凭借高效的平衡维护和稳定的时间复杂度，成为了数据管理的得力助手。作为 C++ 算法小白，掌握红黑树的原理和应用，能让我们在算法学习和编程实践中更上一层楼！