NGINX下的红黑树源码详解（附 流程图和GIF）（1）：https://developer.aliyun.com/article/1415930
那我们就接着之前的gif继续吧
涉及到的 3/4、5情况（精简版）
情况3：变化前[当前结点为4节点]：
当前节点的父节点是红色且祖父节点的另一个子节点（叔叔节点）是红色。
对策：将当前节点的父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，从新的当前节点重新开始算法。
情况4：[当前节点为7节点]：
当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子
对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。
情况5：[当前节点为2节点]
当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子
对策：父节点变为黑色，祖父节点变为红色，把祖父节点右旋
下面是屏幕截图：（实在觉得网页不够看，博主鼓励多开几个！！！）
看到没有，以上就只是对着原理进行分析都能这么长（相信大家应该知道了吧），但是有时候知道原理并不代表你能看懂代码（博主亲身体验！！）所以博主就对着代码来给大家分析一下红黑树染完色之后的左右旋吧（只讲左右旋就已经很复杂了。希望大家对红黑树的理解更加深刻！！！！！）
下面是情况四的左旋:
我就把有用的代码粘过来了:
//之前博客的情况4 } else { //如果父结点的右兄弟是黑的 if (node == node->parent->right) { //如果新结点是右子结点 node = node->parent; //父结点成为新node ngx_rbtree_left_rotate(root, sentinel, node); //node左旋 --->跳转到子函数 } //左旋 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->right = temp->left; ///node的右节点设置为他原来右节点的左节点 if (temp->left != sentinel) { //如果右子结点的左结点不为哨兵 temp->left->parent = node; //右子结点的左子结点挂在左旋结点上 } temp->parent = node->parent; //右节点将会变成原来node的父节点。 if (node == *root) { //是不是根节点的判断 *root = temp; } else if (node == node->parent->left) { //然后把右节点的信息和原来node的parent进行维护 node->parent->left = temp; } else { node->parent->right = temp; } temp->left = node; //现在node变回他原来右节点的子节点了 node->parent = temp; //所以他的parent变成temp }
染色的博主就不管了,博主这个GIF只是针对于旋转代码是如何弄的。
虽然说上面的连线是有点乱的，但是精髓博主全部都讲到了，好好理解一定能掌握的！！！！(我只能穿模糊的了,大家可以自己找到原图跟着博主的思路)
画图太小，导致有一条语句丢失，博主画完图又仔细看了一下逻辑，不然大家可能会接受到不完成的旋转
最后的图片，大家可以对照：
经过情况四之后的情况五的右旋:
ngx_rbt_black(node->parent); //node的父结点染黑 ngx_rbt_red(node->parent->parent); //node的父结点的父结点染红 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);//node的父结点的父结点右旋 ---->跳转到子函数 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变回他原来左节点的子节点了 node->parent = temp; //所以他的parent变成temp }
再看看我们的插入代码是不是会有感觉了呢??
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; //树根指针赋给了root sentinel = tree->sentinel; //哨兵指针赋给了哨兵指针 //如果树是空树的话,那么插入的结点就会变成根节点,伴随着的左右子节点就会变成哨兵 if (*root == sentinel) { //特判，如果根是哨兵，即树是空的 node->parent = NULL; //新插入的结点变成了根 node->left = sentinel; //新结点的左子结点是哨兵 node->right = sentinel; //新结点的右子结点也是哨兵 ngx_rbt_black(node); //新根染黑 *root = node; //确认新结点为新根 return; //插入结束 } //树初始化时给了insert指针一个函数地址 //查看前面的宏ngx_rbtree_init(tree, s, i) //发现只是把指定结点染黑，同时赋为根和哨兵，给insert指针指定一个函数 //ngx_rbtree.c中有两个参数表符合的可选函数：插入值、插入计时器值 //稍后来看两种插入分别如何实现又有什么区别 // insert 就对应 .h的那一个函数指针(61,54 行就能看懂了) // 函数指针里面的参数有 根节点、插入结点、哨兵结点的指针 tree->insert(*root, node, sentinel); //插入操作(通过这个函数指针的调用就能找到我们的插入点了) /* 若红黑树不为空，则按照二叉查找树的插入操作进行 * 该操作由函数指针提供(跳转到插入函数) */ /* re-balance tree */ //如果新结点不是根结点而且其父结点是红的，循环 while (node != *root && ngx_rbt_is_red(node->parent)) { //最坏的情况,就是 情况:3,4,5全部走一遍 // 之前博客的情况3 if (node->parent == node->parent->parent->left) { //如果父结点是左子结点，temp 获得父结点的右兄弟 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; //父结点的父结点成为当前结点,继续去维护红黑树性质 //之前博客的情况4 } else { //如果父结点的右兄弟是黑的 if (node == node->parent->right) { //如果新结点是右子结点 node = node->parent; //父结点成为新node ngx_rbtree_left_rotate(root, sentinel, node); //node左旋 --->跳转到子函数 } //之前博客的情况5 ngx_rbt_black(node->parent); //node的父结点染黑 ngx_rbt_red(node->parent->parent); //node的父结点的父结点染红 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);//node的父结点的父结点右旋 ---->跳转到子函数 } } //与上面的情况对称 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); //根结点染黑,因为根节点必须为黑色 } //然后是对应ngx_rbtree_insert_pt指针的基础的结点插入函数： //上文提到nginx提供一种机制自定义插入函数解决key值冲突，不过nginx提供几个默认的供我们使用： //root是容器指针 //node是待插入节点指针 //sentinel是哨兵节点 //向红黑树插入节点，每个节点key都是唯一的 void ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) {//根节点temp、插入结点node、哨兵结点的指针sentinel ngx_rbtree_node_t **p; for ( ;; ) {//无条件循环或者说死循环，等同于while(1)但节省了一个字符,为了找到插入点 p = (node->key < temp->key) ? &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); } 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->right = temp->left; ///node的右节点设置为他原来右节点的左节点 if (temp->left != sentinel) { //如果右子结点的左结点不为哨兵 temp->left->parent = node; //右子结点的左子结点挂在左旋结点上 } temp->parent = node->parent; //右节点将会变成原来node的父节点。 if (node == *root) { //是不是根节点的判断 *root = temp; } else if (node == node->parent->left) { //然后把右节点的信息和原来node的parent进行维护 node->parent->left = temp; } else { node->parent->right = temp; } temp->left = node; //现在node变回他原来右节点的子节点了 node->parent = temp; //所以他的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变回他原来左节点的子节点了 node->parent = temp; //所以他的parent变成temp }
另一种情况就是我们的镜像了,就不再演示
流程图（画的比教粗糙）：
以上就是我们 NGINX有关红黑树插入的全部内容了。上面GIF有点模糊所以想要看完整的视频可以点击我的百度网盘进行观看
本博客篇幅已经够长了如果博主再讲解红黑树的删除只怕打架承受不住，所以想要了解删除的，期待博主的下一篇博客吧。
