treered-black-tree

Can a red-black tree have a black node with a single black child?


When describing the deletion procedure for red-black trees, Arge and Lagoudakis focus on the case when the node to be deleted is black and has a single black child (illustrated in Figure 16 of the CP230 lecture notes here and reproduced below):

Figure 16 from Arge and Lagoudakis (2002)

However, following the description given on Wikipedia here (which follows CLRS), it would seem that a node with a single black child would also have a black NIL (leaf) node as its other child. This would immediately create root-leaf paths in a red-black tree that contain different numbers of black nodes. Those that go from the root to the NIL node would have one less than those that go through the child. So it would seem to me that the case considered by Arge and Lagoudakis could never arise. So my question is: can a red-black tree have a black node with a single black child?


Solution

  • You’re completely right that a black node in a red-black tree can’t have exactly one black child. My understanding - which may be incorrect - is that the algorithm they are describing for deletion contains a case where a black node with no children can be pushed higher up into the tree. (The idea is to either fix the violation locally or to push the violation up toward the root where it can easily be dealt with.) In the course of doing so, it’s possible that the black node being pushed higher up might end up having exactly one black child. By defining this case as “the black node has zero children or one black child,” the logic here can be applied recursively to move the node upward, even if the node couldn’t initially begin with one black child.