|
Let current refer to the node whose parent and siblings are queried in a deleteion step. Initially current is the node selected for deletion. Suppose it has two children. Then another node is selected for deletion instead: namely, either a successor of current (a leaf or a node with only a right child of next greater value), or a predecessor of current (a leaf or node with only a left child of next smaller value). Either is easy to find and rules for doing so are in the next section. The deleted successor or predecessor is saved until the run terminates and then it replaces the node originally selected to be deleted. If a successor or predecessor is necessary, it becomes current when it is found. Due to the use of a successor, only nodes with at most one child need to be considered for deletion.
Assume current initially has at most one child. Consider five cases (with labels - the red ones are impossible cases):
| Current is a red leaf.
| | Current (to be deleted) is node number 46 on the left. The result is shown on the right |
| |
[1]: action: If a successor or predecessor is used, replace the node selected for deletion with the leaf. Otherwise just delete the leaf. The definition of red/black trees is not violated. |
| | | | Current is red with one child.
| [2]: action: This is impossible since the child must be black to avoid two reds in a row on a path but then the number of blacks on paths through the left side of the node is different from the number of blacks on paths through the right side. |
| | | | Current is black with one black child.
| [3]: action: This is impossible since the number of blacks on paths through the left side of the node is different from the number of blacks on paths through the right side. |
| | | | Current is black with one red child.
| | Current (to be deleted) is node number 32 on the left. Result is shown on the right. |
| |
[4]: action: The child must be a leaf, otherwise the definition of red/black trees is violated. Unhook current from the tree and make current's child a child of current's former parent (there is one non-violating way to do it). If current is a successor or predecessor, it replaces the node selected for deletion. Otherwise current is deleted. There is no violation of the definition of red/black trees since the only change is that a red leaf is deleted. |
| | Current is black and has no children.
| [5]: This step may be reached immediately or through Step [5.1.2] or [5.2.1]. If immediately, current is either the node selected for deletion, or the successor node, or the predecessor node. In all three cases unhook it from the tree (that is, replace it in the tree with a sentinel), but retain the notion of parent, sibling and such as though it is still in the tree because it may be needed in one or more steps below. If current is the root, just delete it and terminate.
The important invariant that holds at this point is the following: the black node count on all paths through (the possibly "phantom") current, and only those paths through current, is short by one and there are no double red violations anywhere in the tree.
The rules below either maintain the invariant as current rises in the tree or find a way to increase the black node count on paths through current. Specifically, either a black must be added to the path through current or the black node count on all other paths must be reduced. There are three cases to consider:
| | Current's sibling is red.
| | Current's sibling is black with two black children.
| The black node count in the sibling's tree is reduced to match the count in current's subtree. In the lucky event that a double red is caused, set the uppermost of the pair, which is parent to current and its sibling, to black. In that case all violations are eliminated; replace the node selected for deletion with successor or predecessor, if there was one, and terminate. There are two action steps:
| | Current is node number 240, the sibling is 80. The sibling's black children are 40 and 120. The parent is 160. The result of this step is shown below. |
[5.2.1]: action: Make the sibling red. This satisfies the goal but may introduce a double red violation at the parent and sibling. Let the parent of current be the new current. If current is black, there is no double red violation and all paths through it are short 1 black. Then the situation described in Step [5] applies so continue to Step [5]. | | | | | Current is node number 160. |
[5.2.2]: action: Otherwise, current is red. Make it black. All paths now have the proper black node count and there are no double red violations. In this case, replace the node selected for deletion with successor or predecessor, if there was one, and terminate. |
|
| | Current's sibling is black with one or two red children.
| The opportunity to rotate a black into current's path now exists. We refer to this rotation below as the final rotation (which always happens) to distinguish it from a preliminary rotation (which may or may not happen) that is described later. We have to be careful about the after-final-rotation sibling of current, though: if it is red and the parent is red there will be a double red violation. This can be solved by making the red pre-final-rotation parent black before the final rotation. Unfortunately, if the pre-final-rotation sibling is black, the black node count through current will then be raised by 2 after the final rotation. This can be solved by making the black pre-final-rotation sibling red if its pre-final-rotation parent is red (the parent will then be turned black). This coloring policy results in the correct black node count through current as well as its after-final-rotation sibling, provided the pre-final-rotation sibling is black.
But it is possible that the pre-final-rotation sibling is red (therefore the pre-final-rotation parent is black). Since, in this case, it is required for the sibling to be black initially, the only way this could happen is by means of the preliminary rotation, yet to be described. But that rotation would have pulled a black out of the "near" nephew's path. If we extend the above mentioned sibling coloring policy to require the sibling to take the color of the parent before the final rotation, that black is restored. Hence when the near nephew's tree is moved to be a sibling of current on the final rotation, its black node count is unchanged, even if the pre-final-rotation sibling had been red.
Moreover, the above operations introduce no double red violations.
So, the only problem is that the black node count on current's "far" nephew before final rotation (which is current's parent's sibling after rotation) will be reduced by 1. This is easily taken care of by making the "far" nephew black if it had been red. Doing so also eliminates the possibility of a double red violation due to the former sibling becoming red.
But, if the "far" nephew had been black, a red must be moved into the "far" nephew side from the "near" nephew (this is possible since there must be at least one red nephew) by a preliminary rotation around the sibling. That red could be set to black to increase the black node count on the sibling side. But if the parent were also set to black from red, as described above, the count will be increased too much. Luckily, the afore mentioned policy of setting the sibling's color to that of its parent before the final rotation ensures this does not happen.
Thus, there are two or three action steps depending on whether current's "far" nephew is black before any rotations take place:
| | Current is node number 54, the "far" nephew is node number 7, the sibling is 20. After rotation (shown below), the new sibling and old "near" nephew is 30. |
[5.3.1]: action: If the "far" nephew is black, rotate in that direction around the sibling. This is the preliminary rotation referred to above. Current's new (pre-final-rotation) sibling is its old (pre-preliminary-rotation) "near" nephew which must be red. The purpose of this step is to fix the potential problem that the black node count of paths through current's (pre-preliminary-rotation) "far" nephew become 1 short once the black node is rotated into current's path (after the final rotation). By rotating the "near" nephew red in here, we have the opportunity to pick up a black in the "far" nephew's path in the next step. | | | | | After the preliminary rotation above. The "far" nephew is 20, the sibling is 30 and the parent is 40. The result of this step is shown below. |
[5.3.2]: action: The "far" nephew and sibling of this step may differ from the original "far" nephew and sibling due to the rotation of Step [5.3.1]. Set the color of current's "far" nephew to black, set the color of current's sibling to the color of its parent, set the parent's color to black. One or more of these nodes may already have been the color it or they was or were set to. It is simply easier to set the colors without checking first to see what they are.
If current's pre-final-rotation parent is red, we risk the possibility of a post-final-rotation double red violation between the parent and current's post-final-rotation sibling. To prevent this, the parent is made black. But that will increase the black node count through current by one too many if current's pre-final-rotation sibling is black. So, in that case the pre-final-rotation sibling is made red. If the pre-final-rotation sibling has been rotated in from [5.3.1] and the parent is black, it needs to be changed to black to keep the "far" nephew's black count the same after final rotation. But, if the parent had been red before the final rotation, then the rotated-in pre-final-sibling must remain red otherwise the black node count through the "far" nephew will be too high by 1 after final rotation. The simple rule color the "far" nephew black, make the sibling color the same as the color of its parent, color the parent black satisifes the above. | | | | | After setting colors as above. The result of this step is shown below. |
[5.3.3]: action: Rotate around the parent in the direction of current. This is the final rotation. If there is a successor or predecessor, it replaces the node selected for deletion. The algorithm terminates. | | | | | After the final rotation. |
|
|
|
|
|
|
|