Editing Red–black tree (section)

==== Simple cases ====
* When the deleted node has '''2 children''' (non-NULL), then we can swap its value with its in-order successor (the leftmost child of the right subtree), and then delete the successor instead. Since the successor is leftmost, it can only have a right child (non-NULL) or no child at all.
* When the deleted node has '''only 1 child''' (non-NULL). In this case, just replace the node with its child, and color it black.
** The single child (non-NULL) must be red according to [[#con5|conclusion 5]], and the deleted node must be black according to [[#req3|requirement 3]].
* When the deleted node '''has no children''' (both NULL) and is the root, replace it with NULL. The tree is empty.
* When the deleted node '''has no children''' (both NULL), and '''is red''', simply remove the leaf node.
* When the deleted node '''has no children''' (both NULL), and '''is black''', deleting it will create an imbalance, and requires a rebalance, as covered in the next section.