1. 结点结构
#include <stdio.h>
#include <stdlib.h>

#define RED 1
#define BLACK 0

struct RBNode {
    int key;
    int color;
    struct RBNode* left;
    struct RBNode* right;
    struct RBNode* parent;
};

这里比普通 BST 多了两个东西：

color：颜色
parent：父指针，方便往上找父亲、爷爷、叔叔

2. 创建新结点
struct RBNode* createNode(int key)
{
    struct RBNode* node =
        malloc(sizeof(struct RBNode));

    node->key = key;
    node->color = RED;   // 新插入结点默认红色
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;

    return node;
}

注意：

node->color = RED;

因为新节点染红不增加黑高。

3. 左旋

左旋处理 RR 或 RL 变形之后的情况。

void leftRotate(struct RBNode** root, struct RBNode* x)
{
    struct RBNode* 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;
}

可以理解成：

x 往左下沉
y 上来当新的子树根

形状：

    x
     \
      y

左旋后：

      y
     /
    x

4. 右旋
void rightRotate(struct RBNode** root, struct RBNode* y)
{
    struct RBNode* 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->left)
    {
        y->parent->left = x;
    }
    else
    {
        y->parent->right = x;
    }

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

形状：

      y
     /
    x

右旋后：

    x
     \
      y

5. BST 插入

先按普通 BST 插进去。

void bstInsert(struct RBNode** root, struct RBNode* node)
{
    struct RBNode* parent = NULL;
    struct RBNode* cur = *root;

    while(cur != NULL)
    {
        parent = cur;

        if(node->key < cur->key)
        {
            cur = cur->left;
        }
        else
        {
            cur = cur->right;
        }
    }

    node->parent = parent;

    if(parent == NULL)
    {
        *root = node;
    }
    else if(node->key < parent->key)
    {
        parent->left = node;
    }
    else
    {
        parent->right = node;
    }
}

这一步只保证：

左 < 根 < 右

颜色还没修。

6. 插入修复 fixInsert

这是红黑树插入最核心。

void fixInsert(struct RBNode** root, struct RBNode* node)
{
    while(node != *root &&
          node->parent->color == RED)
    {
        struct RBNode* parent = node->parent;
        struct RBNode* grand = parent->parent;

        if(parent == grand->left)
        {
            struct RBNode* uncle = grand->right;

            if(uncle != NULL && uncle->color == RED)
            {
                parent->color = BLACK;
                uncle->color = BLACK;
                grand->color = RED;

                node = grand;
            }
            else
            {
                if(node == parent->right)
                {
                    node = parent;
                    leftRotate(root, node);

                    parent = node->parent;
                    grand = parent->parent;
                }

                parent->color = BLACK;
                grand->color = RED;
                rightRotate(root, grand);
            }
        }
        else
        {
            struct RBNode* uncle = grand->left;

            if(uncle != NULL && uncle->color == RED)
            {
                parent->color = BLACK;
                uncle->color = BLACK;
                grand->color = RED;

                node = grand;
            }
            else
            {
                if(node == parent->left)
                {
                    node = parent;
                    rightRotate(root, node);

                    parent = node->parent;
                    grand = parent->parent;
                }

                parent->color = BLACK;
                grand->color = RED;
                leftRotate(root, grand);
            }
        }
    }

    (*root)->color = BLACK;
}
7. 这段代码怎么对应你刚才的理解
情况一：父亲在爷爷左边
        G
       /
      P
     /
    X

代码进入：

if(parent == grand->left)

叔叔是：

struct RBNode* uncle = grand->right;
叔叔红
if(uncle != NULL && uncle->color == RED)
{
    parent->color = BLACK;
    uncle->color = BLACK;
    grand->color = RED;

    node = grand;
}

就是
父黑
叔黑
爷红
当前 = 爷爷
继续往上修
叔叔黑：先处理 LR

如果：

        G
       /
      P
       \
        X

也就是 LR。

代码：

if(node == parent->right)
{
    node = parent;
    leftRotate(root, node);

    parent = node->parent;
    grand = parent->parent;
}

先对 P 左旋，把 LR 变成 LL。

然后统一按 LL 处理：

parent->color = BLACK;
grand->color = RED;
rightRotate(root, grand);

就是：

父亲变黑
爷爷变红
对爷爷右旋
8. 父亲在爷爷右边

这个是完全对称的。

    G
     \
      P
       \
        X

代码进入：

else
{
    struct RBNode* uncle = grand->left;

如果叔叔红：

父黑
叔黑
爷红
当前=爷爷

如果叔叔黑：

先处理 RL，再统一 RR。

9. 外部插入函数
void insertRB(struct RBNode** root, int key)
{
    struct RBNode* node = createNode(key);

    bstInsert(root, node);

    fixInsert(root, node);
}

完整流程就是：

创建红节点
BST 插入
红黑树修复

10. 简单测试打印中序
void inorder(struct RBNode* root)
{
    if(root == NULL)
    {
        return;
    }

    inorder(root->left);

    printf("%d(%s) ",
           root->key,
           root->color == RED ? "R" : "B");

    inorder(root->right);
}
11. main 示例
int main()
{
    struct RBNode* root = NULL;

    insertRB(&root, 10);
    insertRB(&root, 20);
    insertRB(&root, 30);
    insertRB(&root, 15);
    insertRB(&root, 5);

    inorder(root);

    return 0;
}

可能输出类似：

5(R) 10(B) 15(R) 20(B) 30(B)

具体颜色可能因为插入序列和实现细节有差异，但必须满足红黑树性质。

12. 核心代码



while(node != *root &&
      node->parent->color == RED)
{
    if(parent 是 grand 的左孩子)
    {
        uncle = grand->right;

        if(uncle 是红)
        {
            parent黑;
            uncle黑;
            grand红;
            node = grand;
        }
        else
        {
            if(node 是 parent 的右孩子)
            {
                对 parent 左旋;
            }

            parent黑;
            grand红;
            对 grand 右旋;
        }
    }
    else
    {
        完全对称;
    }
}

root黑;


叔叔红：变色并向上继续。
叔叔黑：先把 LR/RL 转成 LL/RR，再旋转，最后父黑爷红。