Draw the red-black tree that results after TREE-INSERT is called on the tree in Figure 13.1 with key 36. If the inserted node is colored red, is the resulting tree a red-black tree? What if it is colored black?
If the resulting node is red, then we violate property 4 because the red node 35 does not have two black children.
If the resulting node is black, then we violate property 5 because the single path to a leaf node child of 35 contains 1 more black node than all other leaf node simple paths.
The following LaTeX code was used to generate the above red-black tree:
\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{arrows}
\tikzset{
treenode/.style = {align=center, inner sep=0pt, text centered,
font=\sffamily},
arn_n/.style = {treenode, circle, white, font=\sffamily\bfseries, draw=black,
fill=black, text width=1.5em},
arn_r/.style = {treenode, circle, red, draw=red,
text width=1.5em, very thick},
arn_x/.style = {treenode, rectangle, draw=black,
minimum width=0.5em, minimum height=0.5em}
}
\begin{document}
\begin{tikzpicture}[level/.style={sibling distance = 6cm/#1,
level distance = 1cm}]
\node [arn_n] {26}
child{ node [arn_r] {17}
child{ node[attribute,xshift=-2mm] [arn_n] {14}
child{ node[attribute,xshift=-2mm] [arn_r] {10}
child{ node[attribute,xshift=-2mm] [arn_n] {7}
child{ node[attribute,xshift=2mm] [arn_r] {3}
child{ node[attribute,xshift=2mm] [arn_n] {nil}}
child{ node[attribute,xshift=-2mm] [arn_n] {nil}}}
child{ node[attribute,xshift=-2mm] [arn_n] {nil}}}
child{ node[attribute,xshift=-2mm] [arn_n] {12}
child{ node[attribute,xshift=3mm] [arn_n] {nil}}
child{ node[attribute,xshift=-3mm] [arn_n] {nil}}}}
child{ node[attribute,xshift=-2mm] [arn_n] {16}
child{ node[attribute,xshift=4mm] [arn_r] {15}
child{ node[attribute,xshift=4mm] [arn_n] {nil}}
child{ node[attribute,xshift=-2mm] [arn_n] {nil}}}
child{ node[attribute,xshift=-3mm] [arn_n] {nil}}}
}
child{ node [arn_n] {21}
child{ node[attribute,xshift=1mm] [arn_n] {19}
child{ node[attribute,xshift=4mm] [arn_n] {nil}}
child{ node[attribute,xshift=-4mm] [arn_r] {20}
child{ node [arn_n] {nil}}
child{ node [arn_n] {nil}}}}
child{ node[attribute,xshift=-1mm] [arn_n] {23}
child{ node[attribute,xshift=4mm] [arn_n] {nil}}
child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
}
}
child{ node [arn_n] {41}
child{ node [arn_r] {30}
child{ node[attribute,xshift=2mm] [arn_n] {28}
child{ node[attribute,xshift=4mm] [arn_n] {nil}}
child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
child{ node [arn_n] {38}
child{ node [arn_r] {35}
child{ node[attribute,xshift=3mm] [arn_n] {nil}}
child{ node[attribute,xshift=-3mm] {36}
child{ node[attribute,xshift=2mm] [arn_n] {nil}}
child{ node[attribute,xshift=-2mm] [arn_n] {nil}}}}
child{ node [arn_r] {39}
child{ node[attribute,xshift=3mm] [arn_n] {nil}}
child{ node[attribute,xshift=-3mm] [arn_n] {nil}}}}
}
child{ node [arn_n] {47}
child{ node [arn_n] {nil}}
child{ node [arn_n] {nil}}
}
}
;
\end{tikzpicture}
\end{document}