small amount of extra storage space for auxiliary variables it is in-place. Removal Simple cases The label N denotes the current node that at entry is the node to be deleted. If N is the root that does not have a non-NIL child, it is replaced by a NIL node, after which the tree is empty—and in RB-shape. If N has exactly one non-NIL child, it must be a red child, because if it were a black one then requirement 4 would force a second black non-NIL child. If N is a red node, it cannot have exactly one non-NIL child, because this would have to be black by requirement 3. Furthermore, it cannot have exactly one black child as argued just above. As a consequence, the red node N is without any child and can simply be removed. If N is a black node, it may have a red child or no non-NIL child at all. If N has a red child, it is simply replaced with this child after painting the latter black. If N has two non-NIL children, an additional navigation to the minimum element in its right subtree (which is N’s in-order successor, say ) finds a node with no other node between N and (as shown here). This node does not have a left child and thus has at most one non-NIL child. If is to be removed in N’s place, the red–black tree data related with N and , i.e. the color of and the pointers to and from the two nodes, have to be exchanged. (As a result, the modified red–black tree is the same as before, except that the order between N and is reversed.) This choice may result in one of the more simple cases above, but if is without child and black we arrive at ... Removal of a black non-root leaf The complex case is when N is not the root, colored black and has no proper child (⇔ only NIL children). In the first iteration, N is replaced by NIL. void RBdelete2( RBtree* T, // -> red–black tree struct RBnode* N) // -> node to be deleted { struct RBnode* P = N->parent; // -> parent node of N byte dir; // side of P on which N is located (∈ { LEFT, RIGHT }) struct RBnode* S; // -> sibling of N struct RBnode* C; // ->