13.1-4

[Donrwalsh]

I believe the solution for exercise 13.1-4 is incorrect. The "0-5" degrees seems to include the parent edge as a degree, but what I've seen is that trees in computer science tend to only count direct descendants in the degree. The absorbing node will have a degree of 2-4 under this definition.

In addition, that the depth of tree leaves will reduce by at most 1/2 is accurate, I think the more noteworthy detail is that all leaf nodes will have the same depth across the entire red-black tree. (This comes from property 5)

This also seems to be the approach that the book's solutions manual takes.

[lfy05]

Agree. The answer should probably be:

2 - both children already black, no absorption can happen; 3 - one child is black and one child is red; 4 - both child are red

[aschroede]

I agree that the maximum degree of a node after the absorption is 4, if we assume that the definition of the degree of a node is the number of children of the node.