Change Details

Consider the lines: if (!L && !R) { S1; continue; } if (!R) S2; You can infer that, in S2, L must be true. We can rewrite as: if (!L && !R) { S1; continue; } if (L) S2; or even as if (L) S2; else if (!R) { S1; continue; } and this change does that rewrite in two places in RB_REMOVE_COLOR, where L and R abbreviate "the left (right) child of tmp is red". In each of the two versions of S2, there is a null test on oleft (oright) which is redundant because we know each to be red, and therefore not null. Those null tests are removed. After each of the rewrites described so far, there is an assignment of black to a node, conditioned on that node being non-null. This node, or null, started the loop iteration as the child of a red node, and is necessarily black already. So the assignment is redundant and it is removed. S2;

Consider the lines: if (!L && !R) { S1; continue; } if (!R) S2; You can infer that, in S2, L must be true. We can rewrite as: if (!L && !R) { S1; continue; } if (L) S2; or even as if (L) S2; else if (!R) { S1; continue; } and this change does that rewrite in two places in RB_REMOVE_COLOR, where L and R abbreviate "the left (right) child of tmp is red". In each of the two versions of S2, there is a null test on oleft (oright) which is redundant because we know each to be red, and therefore not null. Those null tests are removed. After each of the rewrites described so far, there is an assignment of black to a node, conditioned on that node being non-null. In one case, this node, or null, started the loop iteration as the child of a red node, and is necessarily black already. So only make the assignment in the other case, when the node is known to be red, and thus non-null.

Consider the lines: if (!L && !R) { S1; continue; } if (!R) S2; You can infer that, in S2, L must be true. We can rewrite as: if (!L && !R) { S1; continue; } if (L) S2; or even as if (L) S2; else if (!R) { S1; continue; } and this change does that rewrite in two places in RB_REMOVE_COLOR, where L and R abbreviate "the left (right) child of tmp is red". In each of the two versions of S2, there is a null test on oleft (oright) which is redundant because we know each to be red, and therefore not null. Those null tests are removed. After each of the rewrites described so far, there is an assignment of black to a node, conditioned on that node being non-null. TIn one case, this node, or null, started the loop iteration as the child of a red node, and is necessarily black already. SoSo only make the assignment is redundant and it is removed. S2;n the other case, when the node is known to be red, and thus non-null.