Lines Matching full:black
3 Red Black Trees
16 * red-black trees properties: https://en.wikipedia.org/wiki/Rbtree
18 * 1) A node is either red or black
19 * 2) The root is black
20 * 3) All leaves (NULL) are black
21 * 4) Both children of every red node are black
23 * of black nodes.
27 * a black. So if B is the number of black nodes on every simple path (as per
30 * We shall indicate color with case, where black nodes are uppercase and red
105 * If there is a black parent, we are done. in __rb_insert()
142 * Case 2 - node's uncle is black and node is in __rb_insert()
167 * Case 3 - node's uncle is black and node is in __rb_insert()
235 * - node is black (or NULL on first iteration) in ____rb_erase_color()
238 * black node count that is 1 lower than other leaf paths. in ____rb_erase_color()
276 * can be fixed by flipping p to black in ____rb_erase_color()
333 * After rotation, p becomes black, s acquires in ____rb_erase_color()