看代码前请先通过这里下载一份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_ */
ngx_rebtree.c
/* * 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是新根