Linux红黑树(三)——插入节点

客官°小女子只卖身不卖艺 2022-09-19 01:27 165阅读 0赞

### 知识温习： ###

[wiki-red-black tree insert node][]，对插入节点有详细的介绍

[wiki-AVL-tree insert rotate][], 对平衡二叉树旋转调整

### 前言 ###

#### 红黑树的5大“纪律” ####

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色（叶子是NIL节点）。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有[简单路径][Link 1]都包含相同数目的黑色节点。

以上5条，是红黑树“铁”的纪律，任何一条不成立，就不再是一棵红黑树。而红黑树节点的插入会导致原有红黑树中的某些性质不再成立，因此需要对树进行适当的调整(旋转——附带性的改变孩子，改变父亲或者改变颜色)使之依旧是一棵红黑树。下文介绍的就是内核对红黑树插入节点的调整分析！如果对AVL树不了解，树的插入节点不了解，请查看我给予的wiki链接进行温习，否则，你可能会看不明白下文中操作的原因。

### 1、更换孩子节点 ###

static inline void
    __rb_change_child(struct rb_node *old, struct rb_node *new,
    		  struct rb_node *parent, struct rb_root *root)
    {
    	if (parent) {//parent不空，则不是树根
    		if (parent->rb_left == old)//更换是左孩子
    			parent->rb_left = new;
    		else //更换的是右孩子
    			parent->rb_right = new;
    	} else //更换树根
    		root->rb_node = new;
    }

内部函数——只有单一功能实现，不做安全机制，以及高级功能封装，核心一向如此。

###     ###

### 2、旋转辅助函数 ###

__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, struct rb_root *root, int color)
    {
    //获取old的父节点
            struct rb_node *parent = rb_parent(old);
           
    //old's parent and color get assigned to new
            new->__rb_parent_color = old->__rb_parent_color;
    
    //old gets assigned new as a parent and 'color' as a color
            rb_set_parent_color(old, new, color);
    
    //把parent的old孩子替换成new
            __rb_change_child(old, new, parent, root);
    }

### 3、"插入"节点 ###

void rb_insert_color(struct rb_node *node, struct rb_root *root)
    {
    	__rb_insert(node, root, dummy_rotate);
    }
    EXPORT_SYMBOL(rb_insert_color);

很显然，这是对外导出使用的外部函数，真正的功能函数是\_\_rb\_insert（）;

一般刚看到代码时候，会觉得困惑，为什么函数名字叫rb\_insert\_color（），而不是rb\_insert\_node之类的？

原因在上一篇博客中“[核心对红黑树使用两点说明][Link 2]”已经提到——在使用rbtree时候，你需要自己实现你的插入和查询的核心代码。换言之，树节点的插入工作，需要用户自己来完成。核心提供的“插入”只是对用户插入后的节点进行旋转和颜色的调整。函数名叫rb\_insert\_color（）也就理所当然喽^\_^

其中dummy\_rotate是拓展旋转函数，在这里不需要，所以是个空函数。

static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}

核心提供对插入节点后旋转和颜色的调整的内部函数

static __always_inline void
    __rb_insert(struct rb_node *node, struct rb_root *root,
    	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
    {
    	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
    
    	while (true) {
    		/*
    		 * Loop invariant: node is red
    		 *
    		 * If there is a black parent, we are done.
    		 * Otherwise, take some corrective action as we don't
    		 * want a red root or two consecutive red nodes.
    		 */
    		if (!parent) {
    			rb_set_parent_color(node, NULL, RB_BLACK);
    			break;
    		} else if (rb_is_black(parent))
    			break;
    
    		gparent = rb_red_parent(parent);
    
    		tmp = gparent->rb_right;
    		if (parent != tmp) {	/* parent == gparent->rb_left */
    			if (tmp && rb_is_red(tmp)) {
    				/*
    				 * Case 1 - color flips
    				 *
    				 *       G            g
    				 *      / \          / \
    				 *     p   u  -->   P   U
    				 *    /            /
    				 *   n            N
    				 *
    				 * However, since g's parent might be red, and
    				 * 4) does not allow this, we need to recurse
    				 * at g.
    				 */
    				rb_set_parent_color(tmp, gparent, RB_BLACK);
    				rb_set_parent_color(parent, gparent, RB_BLACK);
    				node = gparent;
    				parent = rb_parent(node);
    				rb_set_parent_color(node, parent, RB_RED);
    				continue;
    			}
    
    			tmp = parent->rb_right;
    			if (node == tmp) {
    				/*
    				 * Case 2 - left rotate at parent
    				 *
    				 *      G             G
    				 *     / \           / \
    				 *    p   U  -->    n   U
    				 *     \           /
    				 *      n         p
    				 *
    				 * This still leaves us in violation of 4), the
    				 * continuation into Case 3 will fix that.
    				 */
    				parent->rb_right = tmp = node->rb_left;
    				node->rb_left = parent;
    				if (tmp)
    					rb_set_parent_color(tmp, parent,
    							    RB_BLACK);
    				rb_set_parent_color(parent, node, RB_RED);
    				augment_rotate(parent, node);
    				parent = node;
    				tmp = node->rb_right;
    			}
    
    			/*
    			 * Case 3 - right rotate at gparent
    			 *
    			 *        G           P
    			 *       / \         / \
    			 *      p   U  -->  n   g
    			 *     /                 \
    			 *    n                   U
    			 */
    			gparent->rb_left = tmp;  /* == parent->rb_right */
    			parent->rb_right = gparent;
    			if (tmp)
    				rb_set_parent_color(tmp, gparent, RB_BLACK);
    			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
    			augment_rotate(gparent, parent);
    			break;
    		} else {
    			tmp = gparent->rb_left;
    			if (tmp && rb_is_red(tmp)) {
    				/* Case 1 - color flips */
    				rb_set_parent_color(tmp, gparent, RB_BLACK);
    				rb_set_parent_color(parent, gparent, RB_BLACK);
    				node = gparent;
    				parent = rb_parent(node);
    				rb_set_parent_color(node, parent, RB_RED);
    				continue;
    			}
    
    			tmp = parent->rb_left;
    			if (node == tmp) {
    				/* Case 2 - right rotate at parent */
    				parent->rb_left = tmp = node->rb_right;
    				node->rb_right = parent;
    				if (tmp)
    					rb_set_parent_color(tmp, parent,
    							    RB_BLACK);
    				rb_set_parent_color(parent, node, RB_RED);
    				augment_rotate(parent, node);
    				parent = node;
    				tmp = node->rb_left;
    			}
    
    			/* Case 3 - left rotate at gparent */
    			gparent->rb_right = tmp;  /* == parent->rb_left */
    			parent->rb_left = gparent;
    			if (tmp)
    				rb_set_parent_color(tmp, gparent, RB_BLACK);
    			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
    			augment_rotate(gparent, parent);
    			break;
    		}
    	}
    }

\_\_rb\_insert总流程图：  
![Center][]

这个图能给人一个整个函数全部操作的直观感受，但是依旧不容易理解具体细节。为了解析明白，我下面将要把这个函数进行肢解，简化成不同情况，逐个分析，示例化和图片化。

#### 3.1、 case 1 ####

static __always_inline void
    __rb_insert(struct rb_node *node, struct rb_root *root,
    	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
    {
    	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
    
    	while (true) {
    		if (!parent) {//picture 1
    			rb_set_parent_color(node, NULL, RB_BLACK);
    			break;
    		} else if (rb_is_black(parent)) //picture 2
    			break;
    		}
    	}
    }

![20131223224019328][]

#### 3.2、case 2 ####

//case 2
    static __always_inline void
    __rb_insert(struct rb_node *node, struct rb_root *root,
    	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
    {
    	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
    
    	//picture 3
    	while (true) {
    		....
    		//经过第一关(case 1)这里parent一定是红色节点：8
    		gparent = rb_red_parent(parent); //gparent一定是黑色：13
    		tmp = gparent->rb_right;//17
    
    		if (parent != tmp) {	//成立
    
    			....//省略条件不成立时的代码
    
    			tmp = parent->rb_right;
    
    			....//省略条件不成立时的代码
    
    			gparent->rb_left = tmp;  //（1）
    			parent->rb_right = gparent;//（2）
    			if (tmp)
    				rb_set_parent_color(tmp, gparent, RB_BLACK);//（3）
    			__rb_rotate_set_parents(gparent, parent, root, RB_RED);//（4）
    			break;
    	}
    }

![20131226102432718][]

#### 3.3、case3 ####

//case 3
    static __always_inline void
    __rb_insert(struct rb_node *node, struct rb_root *root,
    	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
    {
    	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
    	
    	//picture 4
    	while (true) {
    		....
    		//经过第一关(case 1)这里parent一定是红色节点：8
    		gparent = rb_red_parent(parent); //gparent一定是黑色：13
    		tmp = gparent->rb_right;//17
    
    		if (parent != tmp) {	//成立
    				if (tmp && rb_is_red(tmp)) {
    						rb_set_parent_color(tmp, gparent, RB_BLACK);//（1）
    						rb_set_parent_color(parent, gparent, RB_BLACK);//（2）
    						node = gparent;//（3）
    						parent = rb_parent(node);//（4）
    						rb_set_parent_color(node, parent, RB_RED);//（5）
    						continue;//从头开始，向上开始新一轮处理
    				}
    				....//省略条件不成立时的代码
    		}
    	}
    }

![20131226102555109][]

#### 3.4、case4 ####

//case 4
    static __always_inline void
    __rb_insert(struct rb_node *node, struct rb_root *root,
    	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
    {
    	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
    
    	//picture 5
    	while (true) {
    		....
    		//经过第一关(case 1)这里parent一定是红色节点：8
    		gparent = rb_red_parent(parent); //gparent一定是黑色：13
    		tmp = gparent->rb_right;//NULL
    
    		if (parent != tmp) {//成立
    
    			....//省略条件不成立时的代码
    			tmp = parent->rb_right;
    			if (node == tmp) {
    				parent->rb_right = tmp = node->rb_left;//（1）
    				node->rb_left = parent;//（2）
    				if (tmp)
    		   		      rb_set_parent_color(tmp, parent,
    						RB_BLACK);//（3）
    				rb_set_parent_color(parent, node, RB_RED);//（4）
    				augment_rotate(parent, node);
    				parent = node;//（5）
    				tmp = node->rb_right;//（6）
    			}
    		gparent->rb_left = tmp; //（7）
    		parent->rb_right = gparent;//（8）
    		if (tmp)
    			rb_set_parent_color(tmp, gparent, RB_BLACK);
    		__rb_rotate_set_parents(gparent, parent, root, RB_RED);//（9）
    		augment_rotate(gparent, parent);
    		break;
    
    	       }
    
    	}
    }

![20131226102812281][]

#### 3.5、其他 ####

while (true) {
    	....gparent = rb_red_parent(parent);
    	tmp = gparent->rb_right;
    
    	if (parent != tmp) {
    	} else {//其他
    	}
    }

对于if-else分支下的几种情况和上面的类似，只是操作进行了"镜面映射"，可”以葫芦画瓢“自行解析！这里不再赘述！

### 4、使用示例 ###

Inserting data into an rbtree
    -----------------------------
    
    Inserting data in the tree involves first searching for the place to insert the
    new node, then inserting the node and rebalancing ("recoloring") the tree.
    
    1-searching for the place to insert thenew node
    2-inserting the node
    3-rebalancing ("recoloring") the tree
    
    The search for insertion differs from the previous search by finding the
    location of the pointer on which to graft(嫁接) the new node.  The new node also
    needs a link to its parent node for rebalancing purposes.
    
    Example:
    
      int my_insert(struct rb_root *root, struct mytype *data)
      {
      	struct rb_node **new = &(root->rb_node), *parent = NULL;
    
      	/* Figure out where to put new node */
      	while (*new) {
      		struct mytype *this = container_of(*new, struct mytype, node);
      		int result = strcmp(data->keystring, this->keystring);
    
    		parent = *new;
      		if (result < 0)
      			new = &((*new)->rb_left);
      		else if (result > 0)
      			new = &((*new)->rb_right);
      		else
      			return FALSE;
      	}
    
      	/* Add new node and rebalance tree. */
      	rb_link_node(&data->node, parent, new);
      	rb_insert_color(&data->node, root);
    
    	return TRUE;
      }

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
    				struct rb_node ** rb_link)
    {
    	node->__rb_parent_color = (unsigned long)parent;
    	node->rb_left = node->rb_right = NULL;
    
    	*rb_link = node;
    }

声明：

>>知识要传播，劳动要尊重! 受益于开源，回馈于社会! 大家共参与，服务全人类!

>>本博文由my\_live\_123原创(http://blog.csdn.net/cwcmcw)，转载请注明出处!   ^\_^

[wiki-red-black tree insert node]: http://en.wikipedia.org/wiki/Red-black_tree
[wiki-AVL-tree insert rotate]: http://en.wikipedia.org/wiki/AVL_tree
[Link 1]: http://zh.wikipedia.org/wiki/%E9%81%93%E8%B7%AF_%28%E5%9B%BE%E8%AE%BA%29
[Link 2]: http://blog.csdn.net/cwcmcw/article/details/17202899
[Center]: /images/20220828/a4e9003b9edc45adbd8ebb4709263de3.png
[20131223224019328]: /images/20220828/558cface762e45ae9f390b278aa3c5ea.png
[20131226102432718]: /images/20220828/799ad19519784ac2b3e00ac3a34804a5.png
[20131226102555109]: /images/20220828/4606c9aed20a46058d88171ab42ded41.png
[20131226102812281]: /images/20220828/8ae6fd7d27114b4190952e07b4b900ef.png