How do I draw merged red black tree into 2,3,4 tree in tikz?

Question

I'm using tikz in study material and I want to show analogy between RB trees and B-trees (2,3,4 tree). I want my output looks something like this example from Wikipedia.

For RB tree I'm using almost exactly same settings as is showed in http://www.texample.net/tikz/examples/red-black-tree/ (just different settings for nil node). I could create 3 nodes in same layer, but it would use manually set position. I also do not know, hot to put these nodes together in rectangle.

Would anybody give me hints or solution? I will be very grateful.

Edit: I've tried this:

    \documentclass{article}
\usepackage{tikz}
\usetikzlibrary{arrows}
\begin{document}

\tikzset{
  treenode/.style = {align=center, inner sep=4pt, text centered,font=\sffamily},
  bnode/.style = {treenode, circle, white, font=\sffamily\bfseries, draw=black, fill=black, text width=1.5em},
  rnode/.style = {treenode, circle, red, draw=red, text width=1.5em, very thick},
  nilnode/.style = {treenode, minimum width=1.3em, minimum height=0.9em}
}

\begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 6cm/#1, level distance = 1.5cm}] 

\node [bnode] {13}
    child[level distance = 0cm]{ node [rnode] {8} 
        child{ node [bnode] {1} 
            child[level distance = 0cm]{ node [nilnode] {Nil} }
            child[level distance = 0cm]{ node [rnode] {6}
                child{ node [nilnode] {Nil} }
                child{ node [nilnode] {Nil} } 
            }
        }
        child{ node [bnode] {11}
            child[level distance = 0cm]{ node [nilnode] {Nil}}
            child[level distance = 0cm]{ node [nilnode] {Nil}}
        }                     
    }
    child[level distance = 0cm]{ node [rnode] {17}
        child{ node [bnode] {15} 
            child[level distance = 0cm]{ node [nilnode] {Nil}}
            child[level distance = 0cm]{ node [nilnode] {Nil}}
        }
        child{ node [bnode] {25}
            child[level distance = 0cm]{ node [rnode] {22}
                child{ node [nilnode] {Nil} }
                child{ node [nilnode] {Nil} } 
            }
            child[level distance = 0cm]{ node [nilnode] {Nil}}
        }
    }
; 
\end{tikzpicture}

\end{document}

Output is this: I need at least the rectangle as border of merged node. If you also know, how to insert some separator (under the arrows in same layer), it would be even better.

//I hope, that now the post meet the rules about question and sorry for previous version.

Answer 1

Since each "node" of the tree has almost everything constant, except the labels, this is a perfect place for an application of pic (requires version 3.0.0 of PGF/TikZ); for further details, please see Section 18 Pics: Small Pictures on Paths of the pgf manual.

The code (some explanatory remarks below):

\documentclass[border=3mm]{standalone}
\usepackage{tikz}
\usetikzlibrary{calc,positioning,fit}

% A command to draw ''NIL'' inside a black box
\newcommand\Nilbox{%
  \normalsize\colorbox{black}{\textcolor{white}{\textsf{\bfseries NIL}}}}

\pgfdeclarelayer{background}
\pgfsetlayers{background,main}

\tikzset{
  NBlack/.style={
    circle,
    minimum size=33pt,
    fill=black,
    draw,
    font=\color{white}\sffamily\large\bfseries
  },
  NRed/.style={
    circle,
    minimum size=33pt,
    fill=red!90!black,
    draw,
    font=\color{white}\sffamily\large\bfseries
  },
  pics/triple/.style args={#1/#2/#3/#4}{
    code={
    \node[NRed] 
      (#4-left) {#1};
    \node[NBlack,right=8pt of #4-left] 
      (#4-middle) {#2};
    \node[NRed,right=8pt of #4-middle] 
      (#4-right) {#3};
    \draw[->,>=latex,thick] 
      (#4-middle) -- (#4-left);  
    \draw[->,>=latex,thick] 
      (#4-middle) -- (#4-right);  
    \begin{pgfonlayer}{background}
      \node[
        name=#4,
        draw,
        inner sep=8pt,
        fill=gray!30,
        dashed,
        fit={(#4-left) (#4-right)}
      ] {};
    \end{pgfonlayer} 
    }
  }
}

\begin{document}

\begin{tikzpicture}
  % the ``nodes''
  \pic {triple=\Nilbox/13/17/lower1};
  \pic[right=15pt of lower1] {triple=\Nilbox/13/\Nilbox/lower2};
  \pic[right=15pt of lower2] {triple=\Nilbox/13/\Nilbox/lower3};
  \pic[right=15pt of lower3] {triple=8/13/17/lower4};
  \coordinate (aux) at ( $ (lower2.east)!0.5!(lower3.west) $ );
  \pic[above=2cm of aux,xshift=-1.4cm] {triple=8/13/17/upper};

  % the arrows between nodes
  \begin{scope}[thick,->,>=latex,shorten >=1pt]
    \draw (upper-left) -- (lower1-middle.50);
    \draw (upper-left) -- (lower2-middle.50);
    \draw (upper-right) -- (lower3-middle.100);
    \draw (upper-right) -- (lower4-middle.120);
  \end{scope}

  % the ''nil'' boxes at the bottom  
  \node[anchor=north east,inner sep=0pt,xshift=-5pt] 
    at (lower1.south east) {\Nilbox};  
  \node[anchor=north east,inner sep=0pt,xshift=-30pt] 
    at (lower1.south east) {\Nilbox};  
  \node[anchor=north west,inner sep=0pt,xshift=5pt] 
    at (lower4.south west) {\Nilbox};  
  \node[anchor=north west,inner sep=0pt,xshift=30pt] 
    at (lower4.south west) {\Nilbox};  
  \node[anchor=north east,inner sep=0pt,xshift=-5pt] 
    at (lower4.south east) {\Nilbox};  
  \node[anchor=north east,inner sep=0pt,xshift=-30pt] 
    at (lower4.south east) {\Nilbox};  
\end{tikzpicture}

\end{document}

The result:

Explanation

Using the pic syntax in the following way

\usetikzlibrary{calc,positioning,fit}

\pgfdeclarelayer{background}
\pgfsetlayers{background,main}

\tikzset{
  NBlack/.style={
    circle,
    minimum size=33pt,
    fill=black,
    draw,
    font=\color{white}\sffamily\large\bfseries
  },
  NRed/.style={
    circle,
    minimum size=33pt,
    fill=red!90!black,
    draw,
    font=\color{white}\sffamily\large\bfseries
  },
  pics/triple/.style args={#1/#2/#3/#4}{
    code={
    \node[NRed] 
      (#4-left) {#1};
    \node[NBlack,right=8pt of #4-left] 
      (#4-middle) {#2};
    \node[NRed,right=8pt of #4-middle] 
      (#4-right) {#3};
    \draw[->,>=latex,thick] 
      (#4-middle) -- (#4-left);  
    \draw[->,>=latex,thick] 
      (#4-middle) -- (#4-right);  
    \begin{pgfonlayer}{background}
      \node[
        name=#4,
        draw,
        inner sep=8pt,
        fill=gray!30,
        dashed,
        fit={(#4-left) (#4-right)}
      ] {};
    \end{pgfonlayer} 
    }
  }
}

allows you to use \pic (or \path pic ...) to draw each of the "nodes" in the form

  \pic {triple=12/5/8/box1};

the last argument ("box1" in the example) is simply a name for the fitting node using in the pic so you can then place other elements using this name; this name is also used to give a name to each of the three circular nodes forming each picture. Inside each \pic, every circular node is internally named <name>-left, <name>-middle, and <name>-right, where <name> is the fourth argument.

Foe example, using

\begin{tikzpicture}
  \pic {triple=12/5/8/box1};
\end{tikzpicture}

will produce

Here, the fitting node (the gray filled rectangle) is assigned the name box1; the circular node labeled "12" is box1-left, the circular node labeled "5" is box1-middle, and the circular node labeled "8" is box1-rught.

Answer 2

Another attempt via Tikz tree. In addtion to the OP's style definitions, this solution added a line style for ease for drawing rectangle box.

Code

\documentclass[12pt]{article}
\usepackage{graphicx,xcolor}
\usepackage[margin=0.5cm]{geometry}
%\usepackage[landscape,paper=ansibpaper]{geometry}
\usepackage{lscape} %for landscape 
\usepackage{tikz}
\usetikzlibrary{shapes,calc,positioning,arrows,mindmap,matrix}

\begin{document}
\tikzset{
  treenode/.style = {align=center, inner sep=4pt, text centered,font=\sffamily},
  bnode/.style = {treenode, circle, white, font=\sffamily\bfseries, draw=black, fill=black, text width=1.5em},
  rnode/.style = {treenode, circle, red, draw=red, text width=1.5em, outer sep=0pt},
  nilnode/.style = {treenode, minimum width=1.3em, minimum height=0.9em, inner sep=6pt},
  line/.style = {very thick, dashed, fill=orange!15!white, fill opacity=0.2}
}
\begin{tikzpicture}[->,>=stealth',
level/.style={sibling distance = 9cm, level distance =2cm},
    level 2/.style={sibling distance=5cm},
    level 3/.style={sibling distance=3cm},
    level 4/.style={sibling distance=2cm},
] 

\node [bnode] {13}
    child[level distance=0]{node [rnode](8) {8} 
        child{node [bnode] {1} 
            child[level distance=0cm]{node [nilnode] (0){Nil} }
            child[level distance=0cm]{node [rnode] (s) {6}
                child[level distance=2cm]{ node [nilnode] {Nil} }
                child[level distance=2cm]{ node [nilnode] {Nil} } 
           }
        }
        child{ node [bnode,xshift=-0.3cm] {11}
            child[level distance = 0cm]{ node [nilnode](1) {Nil}}
            child[level distance = 0cm]{ node [nilnode](2) {Nil}}
        }                     
    }
    child[level distance = 0cm]{ node [rnode](17) {17}
        child{ node [bnode,xshift=0.3cm] {15} 
            child[level distance = 0cm]{ node [nilnode](3) {Nil}}
            child[level distance = 0cm]{ node [nilnode](4) {Nil}}
        }
        child{ node [bnode] {25}
            child[level distance = 0cm]{ node [rnode] (22) {22}
                child[level distance = 2cm]{ node [nilnode] {Nil} }
                child[level distance = 2cm]{ node [nilnode] (6) {Nil} } 
            }
            child[level distance = 0cm]{ node [rnode](27){27}
                child[level distance = 2cm]{ node [nilnode] {Nil} }
                child[level distance = 2cm]{ node [nilnode] {Nil} } 
            }
        }
    }
; 
\draw [line] ($(8.south west)+(-0.3, -0.3)$) rectangle ($(17.north east)+( 0.3, 0.3)$);
\draw [line] ($(0.south west)+(0, -0.3)$) rectangle ($(s.north east)+(0.3, 0.3)$);
\draw [line] ($(1.south west)+(0,-0.3)$) rectangle ($(2.north east)+(0,0.3)$);
\draw [line] ($(3.south west)+(0, -0.3)$) rectangle ($(4.north east)+(0, 0.3)$);
\draw [line] ($(22.south west)+(-0.3, -0.3)$) rectangle ($(27.north east)+(0.3, 0.3)$);
\end{tikzpicture}

\end{document}