nginx笔记：红黑树(二)
则直接重绘为黑色即可 //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_rbtre