justPhukit! Delphi Wiki

Deletion from a RedBlack Tree

Compared with insertion, deletion from a red-black tree is filled with special cases, and can be difficult to follow.

As usual with binary search trees, we start off by searching for the node to be deleted. Like before, we'll have three initial cases: the node has no children (or, in red-black tree terms, both of its children are external nodes); the node has one actual child and one external child; and, finally, the node has two real children. We delete the node in exactly the same way as we did with the standard uncolored binary search tree.

Let's look at these three cases in terms of red-black trees now. The first case has the node with two external children (i.e., the links are nil). By rule 1, these two children are assumed to be black. The node we want to delete, however, can be red or black. Suppose it is red. By deleting it, we replace the parent's child link with a nil pointer—in other words, an external black node. However, we will not have altered the number of black nodes from the new external node to the root, compared with the two paths we had before. Hence, rule 2 is still satisfied. Rule 3 is obviously not violated (we're removing a red node, so we won't run into any problems with this rule). Therefore, the binary tree is still red-black after the deletion. The first transformation in Figure 8.10 shows this possibility.

Figure 8.10: Deletion of a node with two external children

How about the other alternative (the node we remove is black)? Well, here rule 2, the black condition, is well and truly violated. We are reducing the number of black nodes in a path through the tree, by one. The second transformation in Figure 8.10 shows the problem. Let's metaphorically place a bookmark at this point, and consider some more cases.

The second deletion case is the one where we have a single actual child and an external child node. Suppose the node we're deleting is red; its one real child will be black. We can remove the node and replace it with its one child. Rule 2 will not be violated—we're removing a red node after all—and rule 3 does not come into play, so the tree remains red-black. This is the first transformation of Figure 8.11.

Assume now that the node we're removing is black. The one child could be either red or black. Suppose it is red. Rule 2 is going to be violated straight

Figure 8.11: Deletion of a node with one internal and one external child

away since we're removing a black node, and rule 3 may be violated, since the red child's new parent may also be red. However, this case is fairly easy: we merely recolor the red child to be black as we move it up to replace the node being removed. At a stroke we satisfy rule 2 again, and rule 3 does not come into play. The tree is red-black once more. The second transformation in Figure 8.11 shows this possibility.

However, the alternative where the one child is black is not so easy (the third transformation in Figure 8.11). We'll bookmark this problem and consider the third and final deletion case.

The final binary search tree deletion case is not really different from the two we've already considered, because, if you recall, we swap over the node we would like to delete with the largest node from the left child tree and then delete this latter node instead. This latter node is either going to be the first deletion case or the second one, and so we will have to discuss the two bookmarked problems sooner than we thought.

Let's briefly recap. The node we are deleting has at least one external node. If the node we are deleting is red, then its other child must also be black (it can be an external node, of course, since external nodes are automatically black). We can delete the node, replace it with this second child, and the resulting tree is still red-black. If the node we are deleting is black and has one internal child that is red, then we can delete the node and replace it with its one child, recoloring the child black in the process.

If, however, the node we are deleting is black and has at least one external node as a child and the other child is either black or is external, then we have the two problems we identified earlier. The child node being promoted by the deletion is the start of a rule 2 violation (call this the violating node). The last two transformations in Figures 8.10 and 8.11 show these cases.

Let's start whittling away at the individual possibilities. It so happens that we have to take into account the parent and the brother of the violating node and the two children of the brother (the nephews). Notice that we can assume that the brother doe5 have two children (in other words, that the brother is not an external node). Why? Well, consider the original tree. It was red-black; therefore all of the paths that went through the deleted node and the parent had the same number of black nodes as those that went through the brother and the parent. Since we're assuming that the parent is black, and the node we deleted and the child that replaced it were black as well, then all of the paths through the brother must have at least two black nodes in them as well. This translates, at a minimum, to the brother being black and having black nephews.

Anyway, look at the brother node. The following discussion will be easier if the brother is black. If it isn't, recolor the parent red and the brother black, and rotate the parent and promote the brother. This still leaves the tree as red-black except for the original violating node, but it does ensure that the brother node is black. So, from now on, we shall assume that the brother node is black. (Note that if the brother were red, then its children must be black, and furthermore they would have to have children of their own so that rule 2 is originally satisfied. Hence, this transformation still leaves us with a brother with children, as well as a red-black tree.)

The first possibility we shall look at is the one where the violating node has a black parent, and the two nephews are also black. If we recolor the brother red, we shift the problem area up to the parent node, and we can just repeat the full algorithm with that node as the violating node. This possibility is shown in Figure 8.12.

Figure 8.12: Balancing after deletion: the first

The second possibility has a red parent and two black nephews. This is even easier: recolor the parent black and the brother red. The path through the violating node now has the correct number of black nodes again (satisfying rule 2), and the path through the brother node has the correct number of black nodes as well (again, satisfying rule 2). The newly colored red node has a black parent, so we're not violating rule 3. Hence, we have a red-black tree again. Figure 8.13 shows this case.

For the next possibility, suppose that the opposite nephew from the violating node is red. (In other words, if the violating node is a left child of its parent, I'm talking about the right nephew, and if the violating node is a right child, the left nephew.) Recolor this nephew to black. Color the brother the same color as the parent (we don't care what color the parent was originally), and color the parent black. Then rotate the parent to promote the brother. Let's case

Figure 8.13: Balancing after deletion: the second case

take this one carefully, looking at Figure 8.14. Rule 3 first: obviously we haven't introduced any new red nodes so we know that it is satisfied. Now consider rule 2. All paths through the violating node now have an extra black node in them to rectify the problem we had by deleting the original node. All paths through child trees 3 and 4 have the same number of black nodes as before. All paths through the child trees 5 and 6 also have the same number of black nodes as before. Hence, in all cases, we've satisfied rule 2 and therefore the tree is red-black again.

Figure 8.14: Balancing after deletion: the third case

We now consider the last case. Suppose that the opposite nephew is black, but that the one with the same relationship is red. This time we shall do a zig-zag rotation. First, recolor the nephew to be the same color as the parent (again, we don't care what color it was originally), and then recolor the parent black. Second, rotate the brother to promote the nephew, and then rotate the parent to promote the nephew again. Figure 8.15 shows the transformation. Rule 3 hasn't inadvertently been violated anywhere: we haven't introduced any new red nodes. Rule 2: all paths through the violating node have one extra black node so we've removed that problem. All paths through child tree 3 still have the same number of black nodes. Similarly, we can see that all the paths through child trees 4, 5, and 6 have not had an extra black node introduced or removed, so rule 3 still applies. The tree is red-black once again.

There is one ultimate case if we manage to push the violating node all the way up to the root. In this case, the violating node has no parent, and hence has no brother. In this case, it turns out that the violating node is no longer a problem.

Of course, all these cases have mirror-image variants as well, but the analysis of each deletion case will not change. When we code the deletion routine, we shall have to make sure that we cover both the left and right variants properly.

We've at last exhausted all possibilities. There were two recursive steps, or, to be stricter, two steps that required further rebalancing efforts. The first one was that the brother was red, and we wanted it to be black. The second one was that the parent, brother, and nephews were all black. There were three other cases: the parent was red and the brother and nephews were black; the brother was black and the furthest nephew was red (the parent and the nearest nephew were "don't cares"); and finally the brother was black, the furthest nephew was black, and the nearest nephew was red. If you look at Figures 8.12, 8.13, 8.14, and 8.15 you'll see that we've covered all variants.

Without going into the mathematics, it turns out that the red-black deletion algorithm is O(log(n)), although the extra constant time is larger than that of a simple binary tree.

The node deletion operation in a red-black tree is implemented by the code in Listing 8.25.

Listing 8.25: Red-black tree deletion procedure TtdRedBlackTree.Delete(aItem : pointer); var

Node	PtdBinTreeNode;
Dad	PtdBinTreeNode;
Child	PtdBinTreeNode;
Brother	PtdBinTreeNode;
FarNephew	PtdBinTreeNode;
NearNephew	PtdBinTreeNode;
IsBalanced	boolean;
ChildType	TtdChildType;

begin

• find the node to delete; this node will have but one child} Node := bstFindNodeToDelete(altem);
• if the node is red, or is the root, delete it with impunity} if (Node^.btColor = rbRed) or (Node = FBinTree.Root) then begin FBinTree.Delete(Node); dec(FCount); Exit; end;
• if the node's only child is red, recolor the child black, and delete the node}

if (Node~.btChild[ctLeft] = nil) then

Child := Node~.btChild[ctRight] else

Child := Node~.btChild[ctLeft]; if IsRed(Child) then begin Child^.btColor := rbBlack; FBinTree.Delete(Node); dec(FCount); Exit; end;

• at this point, the node we have to delete is Node, it is black, and we know that its one Child that will replace it is black (and also maybe nil!), and there is a parent of Node (which will soon be the parent of Child); Node's brother also exists because of the black node rule}
• if the Child is nil, we'll have to help the loop a little bit and set the parent and brother and whether Node is a left child or not} if (Child = nil) then begin Dad := Node^.btParent;

if (Node = Dad~.btChild[ctLeft]) then begin ChildType ctLeft; Brother := Dad^.btChild[ctRight]; end else begin

ChildType := ctRight; Brother := Dad~.btChild[ctLeft]; end; end else begin

• the following three lines are merely to fool the compiler and remove some spurious warnings} Dad := nil; Brother := nil; ChildType := ctLeft; end;
• delete the node we want to remove, we have no more need of it}

FBinTree.Delete(Node);

dec(FCount);

{in a loop, continue applying the red-black deletion balancing algorithms until the tree is balanced}

repeat

• assume we'll balance it this time} IsBalanced := true;
• we are balanced if the node is the root, so assume it isn't} if (Node<>FBinTree.Root) then begin {get the parent and the brother} if (Node<>nil) then begin Dad := Node^.btParent;

if (Node = Dad~.btChild[ctLeft]) then begin ChildType := ctLeft; Brother := Dad~.btChild[ctRight]; end else begin

ChildType := ctRight; Brother := Dad~.btChild[ctLeft]; end; end;

• we need a black brother, so if the brother is currently red, color the parent red, the brother black, and promote the brother; then go round loop again} if (Brother^.btColor = rbRed) then begin Dad^.btColor := rbRed; Brother^.btColor := rbBlack; rbtPromote(Brother); IsBalanced := false; end
• otherwise the brother is black} else begin
• get the nephews, denoted as far and near} if (ChildType = ctLeft) then begin

FarNephew Brother~.btChild[ctRight]; NearNephew := Brother~.btChild[ctLeft]; end else begin

FarNephew := Brother~.btChild[ctLeft]; NearNephew := Brother~.btChild[ctRight]; end;

• if the far nephew is red (note that it could be nil!), color it black, color the brother the same as the parent, color the parent black, and then promote the brother; we're then done} if IsRed(FarNephew) then begin FarNephew^.btColor := rbBlack; Brother^.btColor := Dad^.btColor; Dad^.btColor := rbBlack; rbtPromote(Brother); end
• otherwise the far nephew is black} else begin
• if the near nephew is red (note that it could be nil!), color it the same color as the parent, color the parent black, and zig-zag promote the nephew; we're then done} if IsRed(NearNephew) then begin NearNephewT.btColor := Dad^.btColor; Dad^.btColor := rbBlack; rbtPromote(rbtPromote(NearNephew)); end
• otherwise the near nephew is also black} else begin
• if the parent is red, color it black and the brother red, and we're done}

if (Dad^.btColor = rbRed) then begin Dad^.btColor := rbBlack; Brother^.btColor := rbRed; end

{otherwise the parent is black: color the brother red and start over with the parent}

else begin

Brother^.btColor := rbRed; Node := Dad; IsBalanced := false; end; end; end; end;

end;

until IsBalanced; end;

Apart from the overridden Insert and Delete methods, there's not much else to the TtdRedBlackTree class. Listing 18.26 shows the interface and the remaining internal method, the one that promotes a node.

Listing 8.26: The TtdRedBlackTree class and node promotion method type

TtdRedBlackTree = class(TtdBinarySearchTree) private protected function rbtPromote(aNode : PtdBinTreeNode) : PtdBinTreeNode; public procedure Delete(aItem : pointer); override; procedure Insert(aItem : pointer); override;

end;

function TtdRedBlackTree.rbtPromote(aNode : PtdBinTreeNode)

: PtdBinTreeNode;

Parent : PtdBinTreeNode; begin

• make a note of the parent of the node we're promoting} Parent := aNode^.btParent;
• in both cases there are 6 links to be broken and remade: the node's link to its child and vice versa, the node's link with its parent and vice versa and the parent's link with its parent and vice versa; note that the node's child could be nil} {promote a left child = right rotation of parent} if (Parent~.btChild[ctLeft] = aNode) then begin Parent~.btChild[ctLeft] := aNode~.btChild[ctRight]; if (Parent~.btChild[ctLeft]<>nil) then

Parent~.btChild[ctLeft]~.btParent := Parent; aNode^.btParent := Parent^.btParent; if (aNode~.btParent~.btChild[ctLeft] = Parent) then aNode~.btParent~.btChild[ctLeft] := anode else aNode~.btParent~.btChild[ctRight] := aNode; aNode~.btChild[ctRight] := Parent; Parent^.btParent := aNode; end

{promote a right child = left rotation of parent}

else begin

Parent~.btChild[ctRight] := aNode~.btChild[ctLeft]; if (Parent~.btChild[ctRight]<>nil) then

Parent~.btChild[ctRight]~.btParent := Parent; aNode^.btParent := Parent^.btParent;

if (aNode~.btParent~.btChild[ctLeft]	= Parent) then
aNode~.btParent~.btChild[ctLeft] :	= anode
else
aNode~.btParent~.btChild[ctRight]	:= aNode;
aNode~.btChild[ctLeft] := Parent;
Parent^.btParent := aNode;
end;
{return the node we promoted}
Result := aNode;
end;

The source code for the TtdRedBlackTree class can be found in the TDBinTre.pas file on the CD.

0 0