看代碼前請先通過這裡下載一份wikipedia關於紅黑樹的介紹，我做了一些批注，結合上面的內容看nginx實現的紅黑樹要簡單一些，不然直接看源碼有點頭痛。
nginx實現的紅黑樹源碼我做了一些注釋，希望對您有點幫助：
ngx_rbtree.h
/* * Copyright (C) Igor Sysoev * Copyright (C) Nginx, Inc. */ #ifndef _NGX_RBTREE_H_INCLUDED_ #define _NGX_RBTREE_H_INCLUDED_ #include#include 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; // 節點的顏色，0表示黑色，1表示紅色 u_char color; // 僅1個字節的節點數據。由於表示的空間太小，所 以一般很少使用。 u_char data; }; typedef struct ngx_rbtree_s ngx_rbtree_t; //如果不希望出現具有相同key關鍵字的不同節點再向紅黑樹添加時出現覆蓋原節點的情況就需要實現自有的ngx_rbtree_insert_bt方法 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; // 指向NIL哨兵節點 ngx_rbtree_node_t *sentinel; // 表示紅黑樹添加元素的函數指針，它決定在添加新節點時的行為究竟是替換還是新增 ngx_rbtree_insert_pt insert;//紅黑樹內部插入函數用於將待插入的節點放在合適的NIL葉子節點處 }; #define ngx_rbtree_init(tree, s, i) \ ngx_rbtree_sentinel_init(s); \ (tree)->root = s; \ (tree)->sentinel = s; \ (tree)->insert = i void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_node_t *node); void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_node_t *node); void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel); void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel); #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) static ngx_inline ngx_rbtree_node_t * ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) {//找到紅黑樹的最小key只需要遍歷至最左 while (node->left != sentinel) { node = node->left; } return node; } #endif /* _NGX_RBTREE_H_INCLUDED_ */
/* * Copyright (C) Igor Sysoev * Copyright (C) Nginx, Inc. */ #include#include /* * The red-black tree code is based on the algorithm described in * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest. */ static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_node_t *node)//紅黑樹容器對外提供的插入API { 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);//將node插入到樹中合適的NIL節點處，此時紅黑樹性質可能被破壞，需要後續重新平衡樹 /* re-balance tree */ while (node != *root && ngx_rbt_is_red(node->parent)) {//插入節點node默認是紅色 //case1:若插入節點node是新根則直接重繪為黑色即可 //case2:若node的父節點是黑色那麼直接插入node即可，case1和case2這兩種簡單的情形不進入while循環體 //此後的情形都是在node為紅色，node->parent為紅色的前提下，破壞了紅黑樹的性質4(紅色節點必有兩個黑色兒子)從而需要調整 if (node->parent == node->parent->parent->left) { temp = node->parent->parent->right;//node的叔父節點temp(右兒子) if (ngx_rbt_is_red(temp)) {//case3：叔父為紅色，重繪父節點node->parent和叔父temp為黑色，此時祖父node->parent->parent可能破壞了性質5(節點所有子孫路徑具有相同數目的黑色節點)，祖父需要重新開始調整 ngx_rbt_black(node->parent); ngx_rbt_black(temp); ngx_rbt_red(node->parent->parent); node = node->parent->parent;//祖父破壞了性質5，從祖父處重新開始調整(祖父作為node從while處開始調整) } else {//叔父temp為黑色或者缺失為NIL節點 if (node == node->parent->right) { //case4: 在叔父temp為黑色或缺失前提下，且祖父node->parent->parent、父節點node->parent、node不在一條直線上，這裡是祖父的左兒子是node的父節點，父節點的右兒子的node // 需要從node的父節點處左旋轉使得祖父、父親、兒子node在一條直線上進入case5，這裡注意旋轉後是原來node和node父節點位置對調了 node = node->parent;//進入case5的是原來的父節點 ngx_rbtree_left_rotate(root, sentinel, node); } //case5: node、node->parent、node->parent->parent均在同一直線上，這裡滿足node->parent->parent->left== node->parent,node->parent->left == node // 且node和node->parent為紅色違背了紅黑樹性質4，且node的叔父node->parent->right為黑色，祖父node->parent->parent為黑色 // 對祖父和父節點的顏色重繪，在node->parent->parent進行右旋 ngx_rbt_black(node->parent); ngx_rbt_red(node->parent->parent); ngx_rbtree_right_rotate(root, sentinel, node->parent->parent); } } else {//這裡和上面的case是對稱的，原理是一樣的，不再重述 temp = node->parent->parent->left; if (ngx_rbt_is_red(temp)) {//case3 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) {//case4 node = node->parent; ngx_rbtree_right_rotate(root, sentinel, node); } //case5 ngx_rbt_black(node->parent); ngx_rbt_red(node->parent->parent); ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); } } } ngx_rbt_black(*root);//對根節點重繪為黑色，當case1插入節點node為新根時該步有用，其他case該步多余但無害處 } void ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)//tree->insert(*root, node, sentinel); {//遍歷樹temp找到node那個合適的插入NIL位置(p) ngx_rbtree_node_t **p; for ( ;; ) { p = (node->key < temp->key) ? &temp->left : &temp->right; //若node->key == temp->key時插入到temp->right位置，若想要自行定義key相同時的方法可以重寫ngx_rbtree_insert方法 if (*p == sentinel) { break; } temp = *p; } *p = node;//p是個NIL就是node帶插入的位置，而temp指向p的父節點 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) {//nginx定義的ngx_rbtree_insert_pt方法，和前面的ngx_rbtree_insert_value性質類似，區別是該方法下的紅黑樹key表示時間或者時間差 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 - (ngx_rbtree_key_int_t) 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) {//紅黑樹的刪除操作，若刪除一個紅色節點不破壞任何性質，但是刪除一個黑色節點破壞了性質5(節點的所有子孫路徑有相同的黑色節點)從而需要重新平衡樹，刪除操作有點復雜 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;//獲取紅黑樹容器的哨兵節點(NIL葉節點) if (node->left == sentinel) {//二叉查找樹的刪除操作都可以歸結為刪除一個只有只有兒子節點的情況，因為假設刪除的節點node有兩個兒子， //會從node的左子樹找一個最大或者右子樹找一個最小的(這兩種情形找到的節點假設為m)替代node的位置，然後node在原來m的位置上從而至多只有一個兒子 temp = node->right; subst = node; } else if (node->right == sentinel) {//這一else 和前面的if說明node只有一個兒子 temp = node->left; subst = node; } else {//node有兩個兒子需要轉換為只有一個兒子的情形 subst = ngx_rbtree_min(node->right, sentinel);//遍歷到node->right的最左 //找到node右子樹最小(左子樹最大也可以，但是nginx實現了ngx_rbtree_min直接調用更加方便)的節點m，交換node和m的位置 if (subst->left != sentinel) {//找到那個非NIL的兒子記為temp temp = subst->left; } else { temp = subst->right; } } //subst是轉換後只有一個兒子的節點(若node有兩個兒子則subst是node右子樹上最小的節點，若node至多只有一個兒子subst==node) if (subst == *root) {//簡單情形1: 待刪除的節點為根節點且該根節點至多只有一個兒子，只用用根節點的兒子替代根節點並重繪新根為黑色即可,if裡面只能是subst==node *root = temp; ngx_rbt_black(temp); /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; return; } red = ngx_rbt_is_red(subst);//是subst為紅色則red為1，否則red為0 if (subst == subst->parent->left) {//將subst和其父節點斷開連接(subst是最終要刪除的節點) subst->parent->left = temp; } else { subst->parent->right = temp; } if (subst == node) {//這是最開始要刪除的節點node本身至多只有一個兒子那麼subst == node temp->parent = subst->parent;//重連subst的兒子(也是node的兒子)到subst的父節點 } else {//node有兩個兒子，那麼subst是node右子樹最小的節點(右子樹最左) if (subst->parent == node) { temp->parent = subst;//該語句感覺沒必要，此處空語句即可 } else { temp->parent = subst->parent; } //將subst替換到node的位置上 subst->left = node->left; subst->right = node->right; subst->parent = node->parent; ngx_rbt_copy_color(subst, node);//拷貝數據 if (node == *root) {//簡單情形2:和簡單情形1不同的是，簡單情形是node至多只有一個兒子，簡單情形2的node有兩個兒子，所以執行到了此處 *root = subst;//直接將新根置為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 node->right = NULL; node->parent = NULL; node->key = 0; if (red) {//簡單情形3：如果subst顏色為紅色，刪除一個紅色節點不會破壞任何性質(注意node和subst位置交換了後刪除操作相當於考察的是原來subst所在位置) return; } /* a delete fixup */ //注意此後都是針對temp操作，因為是temp所在路徑刪除了一個黑色節點(這裡是將subst黑色提到了原來node的位置故少了一個黑色節點)，需要對temp重新平衡 while (temp != *root && ngx_rbt_is_black(temp)) {//簡單情形4：若temp為紅色或者temp是新根，則直接將temp重繪為黑色就行了不用進入循環體 //此後的情形就比前面的幾種情形復雜多了，將用case來替代此後出現的情形，現在的問題是temp所在路徑少了一個黑色 if (temp == temp->parent->left) {//temp為左二子(右兒子是對稱情形) w = temp->parent->right;//找到temp的兄弟w if (ngx_rbt_is_red(w)) {//case2:(注:這裡刪除操作沒有case1直接采用case2是為了和wikipedia保持一致)，對temp父節點左旋轉 ngx_rbt_black(w);//左旋後滿足w->left == temp->parent, temp->parent->left == node且w為黑色，temp->parent為紅色 ngx_rbt_red(temp->parent); ngx_rbtree_left_rotate(root, sentinel, temp->parent); w = temp->parent->right;//temp有了新的兄弟w } if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {//case3:temp的兄弟w為黑色，且w的兩個兒子都是黑色，將w置為黑色後temp和w的黑色節點數相同了，但是temp->parent可能違反了性質4和5，從而轉入temp->parent重新平衡 ngx_rbt_red(w); temp = temp->parent;//注意這裡已經包括了wikipedia上的case4，即temp->parent紅色的話退出while循環直接將其重繪為黑色 } else {//w的左兒子和右兒子顏色不同 if (ngx_rbt_is_black(w->right)) {//case5:w的右兒子為黑色，w的左兒子必為紅色，重繪w->right為黑色，並對w進行右旋然後進入case6 ngx_rbt_black(w->left); ngx_rbt_red(w); ngx_rbtree_right_rotate(root, sentinel, w); w = temp->parent->right;//temp有新的兄弟 } //case6:temp為黑色，w為黑色，w->right紅色,對w左旋後交換temp->parent和w的顏色 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 {//和上面的情形是對稱的 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); } 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; node->right = temp->left; 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; }
