Nginx源碼初探之資料結構 - 紅黑樹資料結構

Nginx紅黑樹介紹

       紅黑樹是Nginx裡的進階資料結構。什麼是紅黑樹呢？紅黑樹是一種平衡二叉樹，簡單的說就是它是一棵空樹，或者左右子樹高差絕對值不超過1，且左右子樹都是平衡二叉樹。時間複雜度O(log n)。除此之外還有如下特性

(1)節點都有顔色，要麼黑色，要麼紅色。

(2)根結點是黑色的，葉子結點是黑色的。

(3)每條從樹到葉子的路上沒有二個連續的紅色。即紅色的子樹一定是黑色，黑色節點的子樹不一定完全是紅色。

(4)各條從葉子到根的路上的黑色結點相同。

其他的内容不再本文叙述，建議自行補充，紅黑二叉樹對比平衡二叉樹了解很容易，多的一點規則就是節點顔色，下圖我根據規則完成了一張節點顔色圖，最主要說明規則3.紅色節點的子樹一定是黑色，如下圖：

1.資料結構

1.1 紅黑樹節點

struct ngx_rbtree_node_s {
    ngx_rbtree_key_t       key;/*關鍵字*/
    ngx_rbtree_node_t     *left;/*左節點指針*/
    ngx_rbtree_node_t     *right;/*右節點之針*/
    ngx_rbtree_node_t     *parent;/*父節點指針*/
    u_char                 color;/*顔色，紅或者黑*/
    u_char                 data;/*資料*/
};
struct ngx_rbtree_s {
    ngx_rbtree_node_t     *root;/*根節點元素*/
    ngx_rbtree_node_t     *sentinel;/*指向NIL節點*/
    ngx_rbtree_insert_pt   insert;/*節點插入操作，可以解決關鍵字沖突*/
};
           

       紅黑樹的節點在很多場景下允許不同的節點擁有相同的關鍵字。例如不同的字元串可能會散列出相同的HASH值（可以參考ngx_hash_t來了解為什麼不同的字元串會散列出相同的HASH值）。這種情況下在添加時就不能覆寫原有節點，而是作為新節點插存在。

2.紅黑樹初始化

#define ngx_rbtree_init(tree, s, i)                                           
    ngx_rbtree_sentinel_init(s);/*初始化sentinel節點，sentinel節點必須是黑色的，參考ngx_rbtree_sentinel_init*/                                              
    (tree)->root = s;                                                          
    (tree)->sentinel = s;                                                     
    (tree)->insert = i/*插入新節點*/
           

3.紅黑色插入節點

        紅黑樹節點插入主要有兩個問題，一個是資料順序的問題，這個滿足平衡二叉樹即可。另一個問題是節點顔色問題，插入操作大部分時間都是在維護顔色的穩定。

void
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  **root, *temp, *sentinel;

    /* a binary tree insert */

    root = &tree->root;
    sentinel = tree->sentinel;
    /*1.如果root節點為nil，則初始化紅黑樹，具體就是：
	*1.父節點為null，這點很容易了解，它自己就是根節點了
	*2.左右節點為sentinel，紅黑樹的葉子節點必須是nil或者null
	*3.節點顔色是黑色，紅黑樹的根節點必須是黑色
	*/
    if (*root == sentinel) {
        node->parent = NULL;
        node->left = sentinel;
        node->right = sentinel;
        ngx_rbt_black(node);
        *root = node;

        return;
    }
    /*2.将節點作為一個新節點插入紅黑樹，需要注意的一點，可能也是大家在學習建構紅黑樹時一直忽略的一點。
	*插入後并沒有完成紅黑樹，紅黑樹為了保證結構的規範性，需要進行一系列的資料調整，調整完成保證資料插入後，**依然是紅黑樹。
	*/
    tree->insert(*root, node, sentinel);

    /* re-balance tree */
    /* 調整紅黑樹，使其滿足性質：紅色的子樹一定是黑色*/
    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);
}