In each of the cases of Figure 13.7, give the count of black nodes from the root of the subtree shown to each of the subtrees ?, ?, . . . , ?, and verify that each count remains the same after the transformation. When a node has a color attribute c or c?, use the notation count (c) or count (c?) symbolically in your count.

Figure 13.7

Transcribed Image Text:

Case 1 B D x A D w B C E x A new w C a Case 2 В с new x В (b) x A D w A D a C E α C E Case 3 в с B )c (с) x A D w x A С пew w B E B D E Case 4 ........ В с D )c (d) x A D w B E B E A c' E a new x — Т.root