Exercise 13.1-1

In the style of Figure 13.1(a), draw the complete binary search tree of height 4 on the keys $\{1, 2, ...., 15\}$. Add the NIL leaves and color the nodes in three different ways such that the black-heights of the resulting red-black trees are 2, 3, and 4.

Black-height = 2:

$13.1-1 Red-Black Tree Black-Height 2$

Black-height = 3:

$13.1-1 Red-Black Tree Black-Height 3$

Black-height = 4:

$13.1-1 Red-Black Tree Black-Height 4$

LaTeX code for black-height = 2:

\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] {8}
    child{ node [arn_r] {4} 
            child{ node [arn_n] {2} 
              child{ node[attribute,xshift=2mm] [arn_r] {1}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_r] {3}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }
            child{ node [arn_n] {6}
              child{ node[attribute,xshift=2mm] [arn_r] {5}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_r] {7}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }                            
    }
    child{ node [arn_r] {12}
            child{ node [arn_n] {10} 
              child{ node[attribute,xshift=2mm] [arn_r] {9}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_r] {11}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }
            child{ node [arn_n] {14}
              child{ node[attribute,xshift=2mm] [arn_r] {13}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_r] {15}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }
    }
; 
\end{tikzpicture}
\end{document}

LaTeX code for black-height = 3:

\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] {8}
    child{ node [arn_n] {4} 
            child{ node [arn_n] {2} 
              child{ node[attribute,xshift=2mm] [arn_r] {1}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_r] {3}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }
            child{ node [arn_n] {6}
              child{ node[attribute,xshift=2mm] [arn_r] {5}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_r] {7}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }                            
    }
    child{ node [arn_n] {12}
            child{ node [arn_n] {10} 
              child{ node[attribute,xshift=2mm] [arn_r] {9}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_r] {11}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }
            child{ node [arn_n] {14}
              child{ node[attribute,xshift=2mm] [arn_r] {13}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_r] {15}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }
    }
; 
\end{tikzpicture}
\end{document}

LaTeX code for black-height = 4:

\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] {8}
    child{ node [arn_n] {4} 
            child{ node [arn_n] {2} 
              child{ node[attribute,xshift=2mm] [arn_n] {1}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_n] {3}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }
            child{ node [arn_n] {6}
              child{ node[attribute,xshift=2mm] [arn_n] {5}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_n] {7}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }                            
    }
    child{ node [arn_n] {12}
            child{ node [arn_n] {10} 
              child{ node[attribute,xshift=2mm] [arn_n] {9}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_n] {11}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }
            child{ node [arn_n] {14}
              child{ node[attribute,xshift=2mm] [arn_n] {13}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
              child{ node[attribute,xshift=-2mm] [arn_n] {15}
                child{ node[attribute,xshift=4mm] [arn_n] {nil}}
                child{ node[attribute,xshift=-4mm] [arn_n] {nil}}}
            }
    }
; 
\end{tikzpicture}
\end{document}