Lines Matching full:red

8  * Red Black Trees.
10  * For now, don't expose Linux Red-Black Trees separately, but retain the
18  * red-black trees properties:  https://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
208          * Loop invariant: node is red.  in rb_insert_augmented()
221          * corrective action as, per 4), we don't want a red root or two  in rb_insert_augmented()
222          * consecutive red nodes.  in rb_insert_augmented()
234                  * Case 1 - node's uncle is red (color flips).  in rb_insert_augmented()
242                  * However, since g's parent might be red, and 4) does not  in rb_insert_augmented()
397                      * if it was red, or by recursing at p.  in rb_erase_color()
398                      * p is red when coming from Case 1.  in rb_erase_color()
424                  * Note: p might be red, and then bot  in rb_erase_color()
425                  * p and sl are red after rotation (which  in rb_erase_color()
540          * Note that if there is one child it must be red due to 5)  in rb_erase_augmented()