transform any -node into parent and two childrenas shown in figure the first child has its own children and xthe second child has children and as beforethe children are colored red and the parent is black -node black -node black either of these is valid -node black figure red transformationsto red-black figure shows tree and the corresponding red-black tree obtained by applying these transformations dotted lines surround the subtrees that were made from -nodes and -nodes the red-black rules are automatically satisfied by the transformation check that this is sotwo red nodes are never connectedand there is the same number of black nodes on every path from root to leaf (or null childyou can say that -node in tree is equivalent to parent with red child in red-black treeand -node is equivalent to parent with two red children it follows that black parent with black child in red-black tree does not represent -node in treeit simply represents -node with another -node child similarlya black parent with two black children does not represent -node