深入理解C++红黑树（从零开始掌握C++红黑树实现方法）

C++红黑树的基本结构

我们首先定义红黑树的节点结构。每个节点包含：键值、颜色、父节点指针、左右子节点指针。

enum Color { RED, BLACK };struct Node {    int key;    Color color;    Node* left;    Node* right;    Node* parent;    Node(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}};

红黑树的核心操作

红黑树的关键在于插入和删除后的修复操作。我们重点讲解插入过程。

1. 插入新节点

首先像普通二叉搜索树一样插入节点，并将其颜色设为红色（避免破坏黑色高度）。然后调用修复函数 fixInsert 来恢复红黑树性质。

class RedBlackTree {private:    Node* root;    Node* NIL; // 代表空叶子节点    void leftRotate(Node* x) {        Node* y = x->right;        x->right = y->left;        if (y->left != NIL)            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(Node* y) {        Node* x = y->left;        y->left = x->right;        if (x->right != NIL)            x->right->parent = y;        x->parent = y->parent;        if (y->parent == nullptr)            root = x;        else if (y == y->parent->right)            y->parent->right = x;        else            y->parent->left = x;        x->right = y;        y->parent = x;    }    void fixInsert(Node* k) {        while (k != root && k->parent->color == RED) {            if (k->parent == k->parent->parent->right) {                Node* u = k->parent->parent->left; // uncle                if (u != NIL && u->color == RED) {                    u->color = BLACK;                    k->parent->color = BLACK;                    k->parent->parent->color = RED;                    k = k->parent->parent;                } else {                    if (k == k->parent->left) {                        k = k->parent;                        rightRotate(k);                    }                    k->parent->color = BLACK;                    k->parent->parent->color = RED;                    leftRotate(k->parent->parent);                }            } else {                Node* u = k->parent->parent->right; // uncle                if (u != NIL && u->color == RED) {                    u->color = BLACK;                    k->parent->color = BLACK;                    k->parent->parent->color = RED;                    k = k->parent->parent;                } else {                    if (k == k->parent->right) {                        k = k->parent;                        leftRotate(k);                    }                    k->parent->color = BLACK;                    k->parent->parent->color = RED;                    rightRotate(k->parent->parent);                }            }        }        root->color = BLACK;    }public:    RedBlackTree() {        NIL = new Node(0);        NIL->color = BLACK;        root = NIL;    }    void insert(int key) {        Node* node = new Node(key);        node->left = NIL;        node->right = NIL;        Node* y = nullptr;        Node* x = root;        while (x != NIL) {            y = x;            if (node->key < x->key)                x = x->left;            else                x = x->right;        }        node->parent = y;        if (y == nullptr)            root = node;        else if (node->key < y->key)            y->left = node;        else            y->right = node;        if (node->parent == nullptr) {            node->color = BLACK;            return;        }        if (node->parent->parent == nullptr)            return;        fixInsert(node);    }};

2. 删除操作（简要说明）

删除比插入更复杂，涉及双黑节点等情况。由于篇幅限制，这里不展开完整代码，但核心思想是：先按 BST 方式删除，若删除的是黑色节点，则需调用 fixDelete 进行颜色调整和旋转，以维持红黑树性质。这是 红黑树插入删除中最难的部分。

为什么学习红黑树？

掌握 C++数据结构教程中的红黑树，不仅能提升你对底层数据结构的理解，还能帮助你在面试中脱颖而出。更重要的是，理解 红黑树平衡算法有助于你设计高性能的程序。

总结

本教程从红黑树的基本性质出发，逐步构建了一个支持插入操作的 C++ 红黑树实现。虽然完整实现（包括删除）较为复杂，但只要理解了旋转和颜色修复的逻辑，就能掌握这一强大的 C++红黑树实现技巧。

建议读者动手编写代码，并配合调试工具观察树的结构变化，加深理解。红黑树虽难，但值得攻克！