图文详解红黑树(上篇)

大家好，这里是物联网心球。今天我们要讲解的是红黑树，相对于数组，哈希表，链表等数据结构，红黑树非常复杂，很多同学都被红黑树的插入和删除操作弄得心态崩溃。本文通过图文详解，让大家彻底搞懂红黑树。为了方便阐述，将图文详解红黑树文章分为上篇和下篇。

1.什么是红黑树？

介绍红黑树之前，我们先了解一下什么是二叉查找树？

图文详解红黑树(上篇) 图1

上图为二叉查找树，二叉查找树需要具备以下几个性质：

每个节点最多只有2个子节点。
左子树所有节点值小于根节点值。
右子树所有节点值大于根节点值。
左右子树也分别满足二叉查找树的性质。

二叉查找树在一般情况下查询效率比链表结构高，具备快速插入、删除查找的特点。由于二叉查找树没有自平衡特性，二叉查找树容易出现极端情况。

图文详解红黑树(上篇) 图2

如上图，新节点一直作为左子节点插入，会让左子树变成一个长长的链表，时间复杂度由O(logN)变为O(N)，这样就失去了快速查找的特性了。红黑树在二叉查找树的基础上，增加了自平衡特性，自平衡特性能够让红黑树时间复杂度保持在O(logN)，所以红黑树是一种自平衡的二叉查找树。

2.红黑树性质

为了能够始终保持自平衡性，红黑树需要具备5个性质，这5个特性是实现红黑树的准则，后面我们要讲解的红黑树插入，删除等操作都要遵循这5个性质：

图文详解红黑树(上篇) 图3

性质1：每个节点要么是红色，要么是黑色。
性质2：根节点必须是黑色。
性质3：每个叶子节点（NULL节点）都是黑色。
性质4：每个红色节点的两个子节点一定都是黑色，即不存在两个连续的红色节点。
性质5：从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节。

只有同时具备以上5个性质才能称为红黑树，下面我们看一下错误示例，我们思考一下，下面这棵红黑树违背了哪些性质。

图文详解红黑树(上篇) 图4

以上红黑树违背了性质4和性质5，所以这颗红黑树不是标准红黑树，性质4和性质5通常是最容易被违背的性质。

3.旋转和变色

旋转和变色是红黑树实现自平衡的重要手段。

3.1 旋转

红黑树旋转可以分为左旋和右旋，红黑树通过左旋和右旋操作，能够在插入和删除元素后，有效地调整树的结构，确保树的高度和平衡性，从而保证高效的查找、插入和删除操作。这些操作是红黑树自平衡机制的重要组成部分 1）左旋以某个节点为支点，其右子节点变为父节点，右子节点的左子节点断开成为原旋转节点的右子节点。

图文详解红黑树(上篇) 图5 2）右旋

以某个节点为支点，其左子节点变为父节点，左子节点的右子节点断开成为原旋转节点的左子节点。

图文详解红黑树(上篇) 图6

3.2 变色

红黑树变色是为了重新符合红黑树的规则，通过调整节点颜色来维持树的平衡。红黑树变色即尝试把红色节点变为黑色，或者把黑色节点变为红色。具体取决于树的结构和需要维持的平衡状态。

图文详解红黑树(上篇) 图7

4.红黑树插入

红黑树插入操作可以分为两步：插入节点和自平衡调整。红黑树插入节点默认为红色，插入节点为红色相对于黑色来说，不容易破坏红黑树性质5，可以降低自平衡调整的复杂度。红黑树插入操作需要遵守以下规则，这些规则都经过了大量实践检验，感兴趣的小伙伴可以自行验证。

图文详解红黑树(上篇) 图8 1）插入根节点图文详解红黑树(上篇) 图9

插入节点为根节点，只需要把根节点变为黑色。

父节点为黑色

图文详解红黑树(上篇) 图10

父节点为黑色，插入节点为红色，插入过程不会违背性质4和性质5，只需要插入节点，不需要做自平衡调整。

3）父节点为红色，叔叔节点为红色

图文详解红黑树(上篇) 图11

（g：祖父节点，f：父节点，u：叔叔节点）父节点为红色，叔叔节点为红色，祖父节点必然为黑色（否则违背性质4）。插入节点为红色，插入节点和父节点都为红色，违背性质4，需要做调整，调整方法为：父节点和叔叔节点变为黑色，祖父节点变为红色。祖父节点变为红色后，如果祖父节点的父节点也为红色，仍然违背性质4，需要以祖父节点为插入节点向上继续调整，直到根节点。

4）父节点为红色，叔叔节点为黑色（LL型，LR型）

图文详解红黑树(上篇) 图12

（g：祖父节点，f：父节点，u：叔叔节点（NULL节点））

LL型：父节点为左子节点，插入节点为左子节点。
LR型：父节点为左子节点，插入节点为右子节点。

新插入节点为红色，父节点为红色，违背性质4，需做调整。LR型需要以f节点为中心进行左旋变为LL型，再按照LL型进行调整。 LL型以祖父节点为中心进行右旋，旋转完毕后，互换祖父节点和祖父节点左子节点颜色。

5）父节点为红色，叔叔节点为黑色（RR型，RL型）

图文详解红黑树(上篇) 图13

（g：祖父节点，f：父节点，u：叔叔节点（NULL节点））

RR型：父节点为右子节点，插入节点为右子节点。
RL型：父节点为右子节点，插入节点为左子节点。

新插入节点为红色，父节点为红色，违背性质4，需做调整。RL型需要以f节点为中心进行右旋变为RR型，再按照RR型进行调整。 RR型以祖父节点为中心进行左旋，旋转完毕后，互换祖父节点和祖父节点右子节点颜色。

5.红黑树插入编程

Linux内核很多模块都使用了红黑树，比如进程调度，epoll机制等。我们参考Linux内核红黑树（rbtree.c）来实现红黑树。 Linux内核数据结构通常会将数据域和节点域进行解耦，从而保证数据结构的通用性。

1）关键数据结构

 struct rb_node { //红黑树节点
    unsigned long  __rb_parent_color; //父节点或节点颜色
    struct rb_node *rb_right; //右子节点
    struct rb_node *rb_left; //左子节点
}__attribute__((aligned(sizeof(long))));

struct rb_root { //红黑树
    struct rb_node *rb_node; //根节点
};

struct pack { //自定义数据
    struct rb_node node; //红黑树节点
    int seq; //节点数值
};
typedef struct pack pack_t;

红黑树数据结构定义很简单，需要注意的是struct rb_node成员__rb_parent_color由两部分组成，最低位为0表示节点为红色，为1表示节点为黑色，其余位表示父节点地址，由于数据是以4字节或8字节对齐，所以可以用一个成员表示两个属性。

2）宏定义

 #define container_of(ptr, type, member) ({ \
    void *__mptr = (void *)(ptr); \
    ((type *)(__mptr - offsetof(type, member))); })

#define RB_RED (0) //红色节点
#define RB_BLACK (1) //黑色节点

//通过节点获取父节点
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))

//通过节点获取自定义数据
#define rb_entry(ptr, type, member) container_of(ptr, type, member)

//初始化红黑树
#define RB_ROOT (struct rb_root) { NULL, }

//红黑树是否为空？
#define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)

//红黑树节点是否为空？
#define RB_EMPTY_NODE(node) \
    ((node)->__rb_parent_color == (unsigned long)(node))
//红黑树节点置空
#define RB_CLEAR_NODE(node) \
    ((node)->__rb_parent_color = (unsigned long)(node))

//红黑树节点查询
#define rb_for_each(node, key, tree, cmp) \
    for ((node) = rb_find_first((key), (tree), (cmp)); \
         (node); (node) = rb_next_match((key), (node), (cmp)))

//提取父节点
#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))

//提取红黑树节点颜色
#define __rb_color(pc) ((pc) & 1)

//红黑树节点为黑色
#define __rb_is_black(pc) __rb_color(pc)

//红黑树节点为红色
#define __rb_is_red(pc) (!__rb_color(pc))

//获取红黑树父节点和颜色
#define rb_color(rb) __rb_color((rb)->__rb_parent_color)

//红黑树节点为红色
#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)

//红黑树节点为黑色
#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)

红黑树实现很复杂，借助一些通用宏定义可以降低代码复杂度。

2）红黑树插入

 void __rb_insert(struct rb_node *node, struct rb_root *root,
        void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
    struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;

    while (true) {
        if (!parent) { //1.插入根节点，设置根节点为黑色
            rb_set_parent_color(node, NULL, RB_BLACK);
            break;
        }

        if(rb_is_black(parent)) //2.父节点为黑色，无需调整
            break;

        gparent = rb_red_parent(parent);

        tmp = gparent->rb_right;
        if (parent != tmp) { //父节点为祖父节点左子节点
            if (tmp && rb_is_red(tmp)) { //3.父节点红色，叔叔节点为红色
                rb_set_parent_color(tmp, gparent, RB_BLACK);
                rb_set_parent_color(parent, gparent, RB_BLACK);
                node = gparent;
                parent = rb_parent(node);
                rb_set_parent_color(node, parent, RB_RED);
                continue;
            }

      //4.父节点为红色，叔叔节点为黑色
            tmp = parent->rb_right;
            if (node == tmp) { //LR型转换为LL型
                tmp = node->rb_left;
                WRITE_ONCE(parent->rb_right, tmp);
                WRITE_ONCE(node->rb_left, parent);
                if (tmp)
                    rb_set_parent_color(tmp, parent,
                                RB_BLACK);
                rb_set_parent_color(parent, node, RB_RED);
                augment_rotate(parent, node);
                parent = node;
                tmp = node->rb_right;
            }

      //LL型调整
            WRITE_ONCE(gparent->rb_left, tmp);
            WRITE_ONCE(parent->rb_right, gparent);
            if (tmp)
                rb_set_parent_color(tmp, gparent, RB_BLACK);
            __rb_rotate_set_parents(gparent, parent, root, RB_RED);
            augment_rotate(gparent, parent);
            break;
        } else { //父节点为祖父节点右子节点
            tmp = gparent->rb_left;
            if (tmp && rb_is_red(tmp)) { //3.父节点红色，叔叔节点为红色
                rb_set_parent_color(tmp, gparent, RB_BLACK);
                rb_set_parent_color(parent, gparent, RB_BLACK);
                node = gparent;
                parent = rb_parent(node);
                rb_set_parent_color(node, parent, RB_RED);
                continue;
            }

        //4.父节点为红色，叔叔节点为黑色
            tmp = parent->rb_left;
            if (node == tmp) { //RL型转换为RR型
                tmp = node->rb_right;
                WRITE_ONCE(parent->rb_left, tmp);
                WRITE_ONCE(node->rb_right, parent);
                if (tmp)
                    rb_set_parent_color(tmp, parent,
                                RB_BLACK);
                rb_set_parent_color(parent, node, RB_RED);
                augment_rotate(parent, node);
                parent = node;
                tmp = node->rb_left;
            }

      //RR型调整
            WRITE_ONCE(gparent->rb_right, tmp);
            WRITE_ONCE(parent->rb_left, gparent);
            if (tmp)
                rb_set_parent_color(tmp, gparent, RB_BLACK);
            __rb_rotate_set_parents(gparent, parent, root, RB_RED);
            augment_rotate(gparent, parent);
            break;
        }
    }
}

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
    __rb_insert(node, root, dummy_rotate);
}

static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) {
    node->__rb_parent_color = (unsigned long)parent;
    node->rb_left = node->rb_right = NULL;
    *rb_link = node;
}

int rb_pack_insert(struct rb_root *root, pack_t *pkt) {
    struct rb_node **new = &(root->rb_node), *parent = NULL;
    printf("**insert pkt seq:%d\n", pkt->seq);
    while(*new) { //查询红黑树，找到匹配节点
        struct pack *p = rb_entry(*new, struct pack, node);
        parent = *new;
        printf("seq:%d\n", p->seq);
        if (pkt->seq < p->seq) {
            new = &((*new)->rb_left);
        } else if (pkt->seq > p->seq) {
            new = &((*new)->rb_right);
        } else {
            printf("insert error\n");
            return -1;
        }
    }

    //插入节点，节点默认为红色
    rb_link_node(&pkt->node, parent, new);
    //红黑树自平衡调整
    rb_insert_color(&pkt->node, root);
    return 0;
}

#define SEQ_NUM (10)
int test_seq[SEQ_NUM] = {100, 90, 150, 120, 77, 20, 11, 5, 199, 160};

int main(int argc, char *argv[]) {
    struct rb_root root = RB_ROOT;

    //生成10个新节点，插入红黑树
    for (int i = 0; i < SEQ_NUM; i++) {
        pack_t *p = (pack_t *)malloc(sizeof(pack_t));
        if (!p) {
            printf("malloc pack error\n");
            return -1;
        }
        p->seq = test_seq[i];
  //红黑树插入
        rb_pack_insert(&root, p);
    }
    rb_pack_delete(&root, 120);
    print_pack_rbtree(&root);

    return 0;
}

红黑树插入操作分为两步：

先遍历红黑树查找匹配的节点，时间复杂度为O(logN)，找到匹配的节点后插入节点。
插入节点后做自平衡调整。（完整代码，请私信博主获取）