红黑树基础

没有写完，以后再补吧。

本文创建于 2024-11-27；修改于 2024-11-27；

1. 红黑树的性质

• 每个结点是红的或者黑的
• 根结点是黑的
• 每个叶子结点是黑的
• 如果一个结点是红的，则它的两个子节点都是黑的
• 对每个结点，从该结点到其子孙结点的所有路径上的包含相同数目的黑结点

// 红黑树节点类
typedef struct _rbtree_node {
    int key;
    void* value;

    struct rbtree_node *left;
    struct rbtree_node *right;
    struct rbtree_node *parent;

    unsigned char color;
} rbtree_node;

// 红黑树类
typedef struct _rbtree {
   struct rbtree_node *root;
   struct rbtree_node *nil;
}

2. 红黑树的旋转

当节点失衡时，对节点进行旋转以保持红黑树的平衡。

a, b, c 代表的是一个个子树：

2.1 左旋

由上面的示意图我们可以得知，左旋时需要更改三对指针:

• y 的左子节点变为 x 的右子节点
  • 如果 y 的左子节点是叶节点，则无需更新其父指针
• 更新父节点指向
  • y->parent 指向 x->parent
  • 如果 x 是 root 节点，则更新该树的 root 节点为 y
  • 判断 x 是左子树还是右子树，对应更新 x->parent->left(right)为 y
• 修改 x, y 的指针
  • y->left=x; x->parent=y;

2.2 右旋

与左旋恰恰相反，略

3. 插入节点

插入节点的默认颜色为红色，根据以下三种情况分别对红黑树进行平衡操作。

3.1 叔节点是红色的

1. 颜色反转

   • 将父节点和叔节点变为黑色。
   • 将祖父节点变为红色。

2. 递归处理

   • 将祖父节点作为新的当前节点，继续向上递归处理，直到根节点或满足其他条件。

3.2 叔节点是黑色的，而且当前节点是 右子节点

1. 左旋

   • 以父节点为轴进行左旋操作

2. 颜色调整

   • 将父节点变为黑色。
   • 将祖父节点变为红色。

3. 右旋操作

   • 以祖父节点为轴进行右旋操作。

3.3 叔节点是黑色的，而且当前节点是 左子节点

1. 右旋操作

   • 以祖父节点为轴进行右旋操作。

2. 颜色调整

   • 将父节点变为黑色。
   • 将祖父节点变为红色。

4. 删除节点

5. 代码

#define RBTREE_ENTRY(name, type) \
    struct name                  \
    {                            \
        struct type *left;       \
        struct type *right;      \
        struct type *parent;     \
        unsigned char color;     \
    }

// 红黑树节点类
typedef int KEY_TYPE;
typedef struct _rbtree_node
{
    KEY_TYPE key;
    void *value;

#if 0
    RBTREE_ENTRY(, _rbtree_node)
    node;
#else
    struct _rbtree_node *left;
    struct _rbtree_node *right;
    struct _rbtree_node *parent;
    unsigned char color;
#endif

} rbtree_node;

// 红黑树类
typedef struct _rbtree
{
    struct _rbtree_node *root;
    struct _rbtree_node *nil;
} rbtree;

void rbtree_left_rotate(rbtree *T, rbtree_node *x)
{
    // 确定失衡节点的右子节点
    rbtree_node *y = x->right;

    // 修改第一对指针
    x->right = y->left;
    // 如果 y 的左子节点不是叶节点则需要更新父指针
    if (y->left != T->nil)
        y->left->parent = x->right;

    // 修改第二对指针
    y->parent = x->parent;
    if (x->parent == T->nil) // 如果 x 是 root 节点
        T->root = y;
    else // 判断 x 是其父节点的左子节点还是右子节点
    {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    };

    // 修改第三对指针
    y->left = x;
    x->parent = y;
}