### 概述 ? ? ? 有關紅黑樹的基礎知識在前面文章中已經做了介紹，想要更詳細的了解紅黑樹可以參考文章《[數據結構-紅黑樹](http://blog.csdn.net/chenhanzhun/article/details/38405041)》，在這里只是單純對 Nginx 中紅黑樹源碼的解析，Nginx 紅黑樹源碼是實現跟算法導論中的講解是一樣的。 ### 紅黑樹結構 ~~~ typedef ngx_uint_t ngx_rbtree_key_t; typedef ngx_int_t ngx_rbtree_key_int_t; /* 紅黑樹節點結構 */ typedef struct ngx_rbtree_node_s ngx_rbtree_node_t; 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; /* */ }; typedef struct ngx_rbtree_s ngx_rbtree_t; 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;/* 指向樹的葉子節點NIL */ ngx_rbtree_insert_pt insert; /* 添加元素節點的函數指針，解決具有相同鍵值，但不同顏色節點的沖突問題； * 該函數指針決定新節點的行為是新增還是替換原始某個節點*/ }; ~~~ ### 紅黑樹的操作 #### 初始化操作 ~~~ /* 給節點著色，1表示紅色，0表示黑色 */ #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) /* 節點著黑色的宏定義 */ /* a sentinel must be black */ #define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node) /* 初始化紅黑樹，即為空的紅黑樹 */ /* tree 是指向紅黑樹的指針， * s 是紅黑樹的一個NIL節點， * i 表示函數指針，決定節點是新增還是替換 */ #define ngx_rbtree_init(tree, s, i) \ ngx_rbtree_sentinel_init(s); \ (tree)->root = s; \ (tree)->sentinel = s; \ (tree)->insert = i ~~~ #### 旋轉操作 ~~~ /* 左旋轉操作 */ static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node) { ngx_rbtree_node_t *temp; temp = node->right;/* temp為node節點的右孩子 */ node->right = temp->left;/* 設置node節點的右孩子為temp的左孩子 */ if (temp->left != sentinel) { temp->left->parent = node; } temp->parent = node->parent; if (node == *root) { *root = temp; } else if (node == node->parent->left) { node->parent->left = temp; } else { node->parent->right = temp; } temp->left = node; node->parent = temp; } static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node) { ngx_rbtree_node_t *temp; temp = node->left; node->left = temp->right; if (temp->right != sentinel) { temp->right->parent = node; } temp->parent = node->parent; if (node == *root) { *root = temp; } else if (node == node->parent->right) { node->parent->right = temp; } else { node->parent->left = temp; } temp->right = node; node->parent = temp; } ~~~ #### 插入操作 ~~~ /* 獲取紅黑樹鍵值最小的節點 */ static ngx_inline ngx_rbtree_node_t * ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) { while (node->left != sentinel) { node = node->left; } return node; } /* 插入節點 */ /* 插入節點的步驟： * 1、首先按照二叉查找樹的插入操作插入新節點； * 2、然后把新節點著色為紅色（避免破壞紅黑樹性質5）； * 3、為維持紅黑樹的性質，調整紅黑樹的節點（著色并旋轉），使其滿足紅黑樹的性質； */ void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_node_t *node) { ngx_rbtree_node_t **root, *temp, *sentinel; /* a binary tree insert */ root = (ngx_rbtree_node_t **) &tree->root; sentinel = tree->sentinel; /* 若紅黑樹為空，則比較簡單，把新節點作為根節點， * 并初始化該節點使其滿足紅黑樹性質 */ if (*root == sentinel) { node->parent = NULL; node->left = sentinel; node->right = sentinel; ngx_rbt_black(node); *root = node; return; } /* 若紅黑樹不為空，則按照二叉查找樹的插入操作進行 * 該操作由函數指針提供 */ tree->insert(*root, node, sentinel); /* re-balance tree */ /* 調整紅黑樹，使其滿足性質， * 其實這里只是破壞了性質4：若一個節點是紅色，則孩子節點都為黑色； * 若破壞了性質4，則新節點 node 及其父親節點 node->parent 都為紅色； */ while (node != *root && ngx_rbt_is_red(node->parent)) { /* 若node的父親節點是其祖父節點的左孩子 */ if (node->parent == node->parent->parent->left) { temp = node->parent->parent->right;/* temp節點為node的叔叔節點 */ /* case1：node的叔叔節點是紅色 */ /* 此時，node的父親及叔叔節點都為紅色； * 解決辦法：將node的父親及叔叔節點著色為黑色，將node祖父節點著色為紅色； * 然后沿著祖父節點向上判斷是否會破會紅黑樹的性質； */ 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 { /* case2：node的叔叔節點是黑色且node是父親節點的右孩子 */ /* 則此時，以node父親節點進行左旋轉，使case2轉變為case3； */ if (node == node->parent->right) { node = node->parent; ngx_rbtree_left_rotate(root, sentinel, node); } /* case3：node的叔叔節點是黑色且node是父親節點的左孩子 */ /* 首先，將node的父親節點著色為黑色，祖父節點著色為紅色； * 然后以祖父節點進行一次右旋轉； */ ngx_rbt_black(node->parent); ngx_rbt_red(node->parent->parent); ngx_rbtree_right_rotate(root, sentinel, node->parent->parent); } } else {/* 若node的父親節點是其祖父節點的右孩子 */ /* 這里跟上面的情況是對稱的，就不再進行講解了 */ 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); } /* 這里只是將節點插入到紅黑樹中，并沒有判斷是否滿足紅黑樹的性質； * 類似于二叉查找樹的插入操作，這個函數為紅黑樹插入操作的函數指針； */ void ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) { ngx_rbtree_node_t **p; for ( ;; ) { /* 判斷node節點鍵值與temp節點鍵值的大小，以決定node插入到temp節點的左子樹還是右子樹 */ p = (node->key < temp->key) ? &temp->left : &temp->right; if (*p == sentinel) { break; } temp = *p; } /* 初始化node節點，并著色為紅色 */ *p = node; node->parent = temp; node->left = sentinel; node->right = sentinel; ngx_rbt_red(node); } void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) { ngx_rbtree_node_t **p; for ( ;; ) { /* * Timer values * 1) are spread in small range, usually several minutes, * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. * The comparison takes into account that overflow. */ /* node->key < temp->key */ p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0) ? &temp->left : &temp->right; if (*p == sentinel) { break; } temp = *p; } *p = node; node->parent = temp; node->left = sentinel; node->right = sentinel; ngx_rbt_red(node); } ~~~ #### 刪除操作 ~~~ /* 刪除節點 */ void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_node_t *node) { ngx_uint_t red; ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; /* a binary tree delete */ root = (ngx_rbtree_node_t **) &tree->root; sentinel = tree->sentinel; /* 下面是獲取temp節點值，temp保存的節點是準備替換節點node ； * subst是保存要被替換的節點的后繼節點； */ /* case1：若node節點沒有左孩子（這里包含了存在或不存在右孩子的情況）*/ if (node->left == sentinel) { temp = node->right; subst = node; } else if (node->right == sentinel) {/* case2：node節點存在左孩子，但是不存在右孩子 */ temp = node->left; subst = node; } else {/* case3：node節點既有左孩子，又有右孩子 */ subst = ngx_rbtree_min(node->right, sentinel);/* 獲取node節點的后續節點 */ if (subst->left != sentinel) { temp = subst->left; } else { temp = subst->right; } } /* 若被替換的節點subst是根節點，則temp直接替換subst稱為根節點 */ if (subst == *root) { *root = temp; ngx_rbt_black(temp); /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; return; } /* red記錄subst節點的顏色 */ red = ngx_rbt_is_red(subst); /* temp節點替換subst 節點 */ if (subst == subst->parent->left) { subst->parent->left = temp; } else { subst->parent->right = temp; } /* 根據subst是否為node節點進行處理 */ if (subst == node) { temp->parent = subst->parent; } else { if (subst->parent == node) { temp->parent = subst; } else { temp->parent = subst->parent; } /* 復制node節點屬性 */ subst->left = node->left; subst->right = node->right; subst->parent = node->parent; ngx_rbt_copy_color(subst, node); if (node == *root) { *root = subst; } else { if (node == node->parent->left) { node->parent->left = subst; } else { node->parent->right = subst; } } if (subst->left != sentinel) { subst->left->parent = subst; } if (subst->right != sentinel) { subst->right->parent = subst; } } /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; if (red) { return; } /* 下面開始是調整紅黑樹的性質 */ /* a delete fixup */ /* 根據temp節點進行處理 ，若temp不是根節點且為黑色 */ while (temp != *root && ngx_rbt_is_black(temp)) { /* 若temp是其父親節點的左孩子 */ if (temp == temp->parent->left) { w = temp->parent->right;/* w為temp的兄弟節點 */ /* case A：temp兄弟節點為紅色 */ /* 解決辦法： * 1、改變w節點及temp父親節點的顏色； * 2、對temp父親節的做一次左旋轉，此時，temp的兄弟節點是旋轉之前w的某個子節點，該子節點顏色為黑色； * 3、此時，case A已經轉換為case B、case C 或 case D； */ if (ngx_rbt_is_red(w)) { ngx_rbt_black(w); ngx_rbt_red(temp->parent); ngx_rbtree_left_rotate(root, sentinel, temp->parent); w = temp->parent->right; } /* case B：temp的兄弟節點w是黑色，且w的兩個子節點都是黑色 */ /* 解決辦法： * 1、改變w節點的顏色； * 2、把temp的父親節點作為新的temp節點； */ if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { ngx_rbt_red(w); temp = temp->parent; } else {/* case C：temp的兄弟節點是黑色，且w的左孩子是紅色，右孩子是黑色 */ /* 解決辦法： * 1、將改變w及其左孩子的顏色； * 2、對w節點進行一次右旋轉； * 3、此時，temp新的兄弟節點w有著一個紅色右孩子的黑色節點，轉為case D； */ if (ngx_rbt_is_black(w->right)) { ngx_rbt_black(w->left); ngx_rbt_red(w); ngx_rbtree_right_rotate(root, sentinel, w); w = temp->parent->right; } /* case D：temp的兄弟節點w為黑色，且w的右孩子為紅色 */ /* 解決辦法： * 1、將w節點設置為temp父親節點的顏色，temp父親節點設置為黑色； * 2、w的右孩子設置為黑色； * 3、對temp的父親節點做一次左旋轉； * 4、最后把根節點root設置為temp節點；*/ ngx_rbt_copy_color(w, temp->parent); ngx_rbt_black(temp->parent); ngx_rbt_black(w->right); ngx_rbtree_left_rotate(root, sentinel, temp->parent); temp = *root; } } else {/* 這里針對的是temp節點為其父親節點的左孩子的情況 */ w = temp->parent->left; if (ngx_rbt_is_red(w)) { ngx_rbt_black(w); ngx_rbt_red(temp->parent); ngx_rbtree_right_rotate(root, sentinel, temp->parent); w = temp->parent->left; } if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { ngx_rbt_red(w); temp = temp->parent; } else { if (ngx_rbt_is_black(w->left)) { ngx_rbt_black(w->right); ngx_rbt_red(w); ngx_rbtree_left_rotate(root, sentinel, w); w = temp->parent->left; } ngx_rbt_copy_color(w, temp->parent); ngx_rbt_black(temp->parent); ngx_rbt_black(w->left); ngx_rbtree_right_rotate(root, sentinel, temp->parent); temp = *root; } } } ngx_rbt_black(temp); } ~~~