3   Red Black Trees
18  * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
20  *  1) A node is either red or black
23  *  4) Both children of every red node are black
28  *  consecutive red nodes in a path and every red node is therefore followed by
32  *  We shall indicate color with case, where black nodes are uppercase and red
33  *  nodes will be lowercase. Unknown color nodes shall be drawn as red within
42 static inline struct rb_node *rb_red_parent(struct rb_node *red)  in rb_red_parent()  argument
44 	return (struct rb_node *)red->__rb_parent_color;  in rb_red_parent()
70 		 * Loop invariant: node is red  in __rb_insert()
74 		 * want a red root or two consecutive red nodes.  in __rb_insert()
96 				 * However, since g's parent might be red, and  in __rb_insert()
241 					 * if it was red, or by recursing at p.  in ____rb_erase_color()
242 					 * p is red when coming from Case 1.  in ____rb_erase_color()