figure an illustration that the red-black tree of figure corresponds to the ( tree of figure based on the highlighted grouping of red nodes with their black parents if is -nodethen keep the (blackchildren of as is if is -nodethen create new red node ygive ' last two (blackchildren to yand make the first child of and be the two children of if is -nodethen create two new red nodes and zgive ' first two (blackchildren to ygive ' last two (blackchildren to zand make and be the two children of notice that red node always has black parent in this construction proposition the height of red-black tree storing entries is (log -( -( or -( figure correspondence between nodes of ( tree and red-black tree( -node( -node( -node