深入理解红黑树（C语言红黑树实现从零开始的详细教程）

C语言红黑树的基本结构定义

我们首先定义红黑树的节点结构。为了简化，我们将使用枚举来表示颜色，并用指针连接父子节点。

#include <stdio.h>#include <stdlib.h>typedef enum { RED, BLACK } Color;typedef struct Node {    int data;    Color color;    struct Node *left;    struct Node *right;    struct Node *parent;} Node;// 红黑树根节点Node *root = NULL;

左旋与右旋操作

旋转是红黑树维持平衡的核心操作。左旋（Left Rotate）和右旋（Right Rotate）用于调整树的结构而不破坏二叉搜索树的性质。

void rotateLeft(Node **root, Node *x) {    Node *y = x->right;    x->right = y->left;    if (y->left != NULL)        y->left->parent = x;    y->parent = x->parent;    if (x->parent == NULL)        *root = y;    else if (x == x->parent->left)        x->parent->left = y;    else        x->parent->right = y;    y->left = x;    x->parent = y;}void rotateRight(Node **root, Node *y) {    Node *x = y->left;    y->left = x->right;    if (x->right != NULL)        x->right->parent = y;    x->parent = y->parent;    if (y->parent == NULL)        *root = x;    else if (y == y->parent->right)        y->parent->right = x;    else        y->parent->left = x;    x->right = y;    y->parent = x;}

插入节点与修复过程

插入新节点时，我们先按普通二叉搜索树的方式插入，并将新节点设为红色。然后根据红黑树的性质进行修复（rebalance），主要处理“双红”冲突。

void insertFixup(Node **root, Node *z) {    while (z != *root && z->parent->color == RED) {        if (z->parent == z->parent->parent->left) {            Node *uncle = z->parent->parent->right;            if (uncle != NULL && uncle->color == RED) {                z->parent->color = BLACK;                uncle->color = BLACK;                z->parent->parent->color = RED;                z = z->parent->parent;            } else {                if (z == z->parent->right) {                    z = z->parent;                    rotateLeft(root, z);                }                z->parent->color = BLACK;                z->parent->parent->color = RED;                rotateRight(root, z->parent->parent);            }        } else {            // 对称情况（右子树）            Node *uncle = z->parent->parent->left;            if (uncle != NULL && uncle->color == RED) {                z->parent->color = BLACK;                uncle->color = BLACK;                z->parent->parent->color = RED;                z = z->parent->parent;            } else {                if (z == z->parent->left) {                    z = z->parent;                    rotateRight(root, z);                }                z->parent->color = BLACK;                z->parent->parent->color = RED;                rotateLeft(root, z->parent->parent);            }        }    }    (*root)->color = BLACK;}Node* createNode(int data) {    Node *node = (Node*)malloc(sizeof(Node));    node->data = data;    node->color = RED;    node->left = node->right = node->parent = NULL;    return node;}void insert(Node **root, int data) {    Node *z = createNode(data);    Node *y = NULL;    Node *x = *root;    while (x != NULL) {        y = x;        if (z->data < x->data)            x = x->left;        else            x = x->right;    }    z->parent = y;    if (y == NULL)        *root = z;    else if (z->data < y->data)        y->left = z;    else        y->right = z;    insertFixup(root, z);}

总结

通过本教程，你已经掌握了如何用 C语言实现红黑树 的核心功能，包括节点定义、旋转操作和插入修复逻辑。红黑树作为重要的平衡二叉搜索树结构，在 Linux 内核、STL（如 std::map）等系统中广泛应用。掌握它不仅能提升你的 C语言数据结构 能力，还能为面试和系统开发打下坚实基础。

建议你动手编写完整代码并测试不同插入序列，观察树的结构变化。实践是掌握 C语言红黑树实现 的最佳方式！