红黑树自底向上插入示例代码

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，再旋转，最后父黑爷红。