红黑树的插入（NGINX源码）

下载并查看NGINX源码

访问NGINX下载页面，找到所需版本

https://nginx.org/en/download.html

使用wget下载源码包，替换版本号为所需版本

wget http://nginx.org/download/nginx-1.24.0.tar.gz

解压源码包

tar -xzvf nginx-1.24.0.tar.gz

进入解压后的目录

cd nginx-1.24.0

红黑树定义

红黑树是每个节点都带有颜色属性的二叉查找树。它是一种自平衡的二叉查找树，能够在插入和删除数据时通过特定操作保持二叉查找树的平衡性，从而获得较高的查找性能。除了二叉查找树的强制要求外，任何一棵有效的红黑树还必须满足以下性质：

节点颜色：每个节点要么是红色，要么是黑色。
根节点：根节点必须是黑色。
叶节点：所有叶节点都是黑色。
红色节点的子节点：红色节点的子节点必须是黑色（即不能有两个连续的红色节点）。
每个节点的黑高：从任何节点到其所有后代叶节点的路径上，必须包含相同数量的黑色节点。

红黑树数据结构

红黑树节点结构体

存储了节点间的对应关系和节点的真实数据。

typedef ngx_uint_t  ngx_rbtree_key_t; // 方便更换key的属性
typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;

struct ngx_rbtree_node_s {
    ngx_rbtree_key_t       key;    // 节点的键值，类型为ngx_rbtree_key_t
    ngx_rbtree_node_t     *left;
    ngx_rbtree_node_t     *right;
    ngx_rbtree_node_t     *parent;
    u_char                 color;
    u_char                 data;    // 节点的数据，类型为u_char，通常存储附加的信息或标记
};

红黑树结构体

维护整个红黑树的根节点及定义插入的节点时执行的函数指针。

typedef struct ngx_rbtree_s  ngx_rbtree_t; 
// 函数指针类型ngx_rbtree_insert_pt定义如何将一个节点插入到红黑树中，可以将不同的插入策略传递给红黑树的操作函数
typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

struct ngx_rbtree_s {
    ngx_rbtree_node_t     *root;
    ngx_rbtree_node_t     *sentinel;
    ngx_rbtree_insert_pt   insert;
};

红黑树插入节点node

给节点染色

#define ngx_rbt_red(node)               ((node)->color = 1)
#define ngx_rbt_black(node)             ((node)->color = 0)
#define ngx_rbt_is_red(node)            ((node)->color)
#define ngx_rbt_is_black(node)          (!ngx_rbt_is_red(node))
#define ngx_rbt_copy_color(n1, n2)      (n1->color = n2->color)

以node为支点右旋

示意图

代码

// 以node为支点右旋
static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
    ngx_rbtree_node_t *node) {

    // 1 标记node的左孩子
    ngx_rbtree_node_t  *temp;
    temp = node->left; 
    
    // 2 改变node的左指针及其左孩子的父指针
    //   如果其左孩子是叶节点，不用将叶节点的父指针指向node
    node->left = temp->right;
    if (temp->right != sentinel) {
        temp->right->parent = node;
    }
    
    // 3 改变temp的父指针，及其可能存在的父节点的孩子指针
    temp->parent = node->parent;
    if (node == *root) {
        *root = temp;
    } else if (node == node->parent->right) {
        node->parent->right = temp;
    } else {
        node->parent->left = temp;
    }

    // 4 改变temp的右指针及其右孩子的父指针
    temp->right = node;
    node->parent = temp;
}

以node为支点左旋

示意图

代码

static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
    ngx_rbtree_node_t *node) {
    
    // 1 标记node的右孩子
    ngx_rbtree_node_t  *temp;
    temp = node->right;

    // 2 改变node的右指针及其右孩子的父指针
    //   如果其右孩子是叶节点，不用将叶节点的父指针指向node
    node->right = temp->left;
    if (temp->left != sentinel) {
        temp->left->parent = node;
    }

    // 3 改变temp的父指针，及其可能存在的父节点的孩子指针
    temp->parent = node->parent;
    if (node == *root) {
        *root = temp;
    } else if (node == node->parent->left) {
        node->parent->left = temp;
    } else {
        node->parent->right = temp;
    }

    // 4 改变temp的左指针及其左孩子的父指针
    temp->left = node;
    node->parent = temp;
}

插入操作

流程图

代码

void ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) {

    ngx_rbtree_node_t  **root, *temp, *sentinel;
    root = &tree->root;    // 获取树的根节点地址，以便进行旋转操作
    sentinel = tree->sentinel;

    // 如果树为空，直接将node节点作为根节点
    if (*root == sentinel) {
        node->parent = NULL;
        node->left = sentinel;
        node->right = sentinel;
        ngx_rbt_black(node);  // 将新节点颜色设为黑色
        *root = node;
        return;
    }

    // node不是根节点不为空，调用插入函数将节点插入到正确位置
    tree->insert(*root, node, sentinel);

    // 当新节点不是根节点且其父节点为红色时，需要进行平衡调整
    while (node != *root && ngx_rbt_is_red(node->parent)) {
        // 如果父节点是祖父节点的左子节点
        if (node->parent == node->parent->parent->left) {
            // 获取叔叔节点（父节点的兄弟节点）
            temp = node->parent->parent->right;

            // 如果叔叔节点是红色
            if (ngx_rbt_is_red(temp)) {
                // 将父节点和叔叔节点都设为黑色，将祖父节点设为红色
                // 然后将祖父节点作为当前节点，继续向上调整
                ngx_rbt_black(node->parent);
                ngx_rbt_black(temp);
                ngx_rbt_red(node->parent->parent);
                node = node->parent->parent;
            }

            // 如果叔叔节点是黑色
            else {
                // 如果新节点是父节点的右子节点
                if (node == node->parent->right) {
                    // 对父节点进行左旋操作
                    node = node->parent;
                    ngx_rbtree_left_rotate(root, sentinel, node);
                }
                // 将父节点设为黑色，祖父节点设为红色
                ngx_rbt_black(node->parent);
                ngx_rbt_red(node->parent->parent);
                // 对祖父节点进行右旋操作
                ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
            }
        } 
        // 如果父节点是祖父节点的右子节点
        else {
            // 获取叔叔节点（父节点的兄弟节点）
            temp = node->parent->parent->left;

            // 如果叔叔节点是红色
            if (ngx_rbt_is_red(temp)) {
                // 将父节点和叔叔节点都设为黑色，将祖父节点设为红色
                // 然后将祖父节点作为当前节点，继续向上调整
                ngx_rbt_black(node->parent);
                ngx_rbt_black(temp);
                ngx_rbt_red(node->parent->parent);
                node = node->parent->parent;
            } 

            // 如果叔叔节点是黑色
            else {
                // 如果新节点是父节点的左子节点
                if (node == node->parent->left) {
                    // 对父节点进行右旋操作
                    node = node->parent;
                    ngx_rbtree_right_rotate(root, sentinel, node);
                }
                // 将父节点设为黑色，祖父节点设为红色
                ngx_rbt_black(node->parent);
                ngx_rbt_red(node->parent->parent);
                // 对祖父节点进行左旋操作
                ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
            }
        }
    }
    // 确保根节点为黑色
    ngx_rbt_black(*root);
}