tree of figure each external node of this red-black tree has black ancestors (including itself)henceit has black depth we use the color blue instead of red alsowe use the convention of giving an edge of the tree the same color as the child node as for previous types of search treeswe assume that entries are stored at the internal nodes of red-black treewith the external nodes being empty placeholders alsowe assume that the external nodes are actual nodesbut we note thatat the expense of slightly more complicated methodsexternal nodes could be null we can make the red-black tree definition more intuitive by noting an interesting correspondence between red-black trees and ( , treesas illustrated in figure namelygiven red-black treewe can construct corresponding ( , tree by merging every red node into its parent and storing the entry from at its parent converselywe can transform any ( , tree into corresponding red-black tree by coloring each node black and performing the following transformation for each internal node vif is -nodethen keep the (blackchildren of as is if is -nodethen create new red node wgive ' first two (blackchildren to wand make and ' third child be the two children of if is -nodethen create two new red nodes and zgive ' first two (blackchildren to wgive ' last two (blackchildren to zand make and be the two children of