[Tex/LaTex] How to draw merged red black tree into 2,3,4 tree in tikz

tikz-treestrees

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.
merged RB tree into B tree

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: my solution using fixed position
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.

Best Answer

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:

enter image description here

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

enter image description here

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.

Related Solutions

[Tex/LaTex] My version of Red-Black Tree

A forest version just because:

forest tree in black and red

\documentclass[tikz]{standalone}

\usetikzlibrary{arrows}
\usepackage{forest}

\begin{document}
  \tikzset{%
    /forest,
    forest node/.style={circle, inner sep=0pt, text centered},
    arn n/.append style={text=white, font=\sffamily\bfseries, draw=black, fill=black, text width=1.5em},
    arn r/.append style={text=red, draw=red, text width=1.5em, very thick},
  }
  \begin{forest}
    for tree={%
      font=\sffamily,
      forest node,
      edge path={
        \noexpand\path[color=black, -stealth', \forestoption{edge}]
          (!u.parent anchor) -- (.child anchor)\forestoption{edge label};
      },
      l sep+=.25cm,
      s sep+=.25cm,
    }
    [1, arn n
      [2, arn r
        [4, arn n
          [6, arn r]
          [7, arn r]
        ]
        [3, arn r, edge label={node[midway, right]{$x$}}, label={right:A}
          [8, arn n]
          [9, arn n]
        ]
      ]
    ]
  \end{forest}

\end{document}

[Tex/LaTex] Text alignment and form of connectors (edges) in tikz tree

If forest is an option:

\documentclass[tikz,border=3mm]{standalone}

\usepackage{forest}
\usepackage[utf8]{inputenc}

\begin{document}

\begin{forest}
for tree={grow'=0,
anchor=west, child anchor=west, fit=band, parent anchor=east, edge path={\noexpand\path[\forestoption{edge}](!u.parent anchor)|-(.child anchor)\forestoption{edge label};}, l sep=1cm,}
[, calign=child,  calign child=2
    [Pressen
           [uniaxiales Pressen]
            [isostatisches Pressen]
            [Vibrationspressen]
            [Stampfen]
        ]
        [Plastisches\\Formen, align=center
            [Extrudieren]
            [Drehen]
        ] 
        [Gießen 
            [Schlickergießen ]
            [Druckgießen ]
            [Spritzgießen ]
            [Foliengießen ]
]
    ]
\end{forest}
\end{document}

enter image description here

2nd version:

I'm not sure to understand what all nodes "raggedright" means, but may be option align=right does it.

The other comment about aligning all same level nodes can be done with tier/.pgfmath=level() option.

\documentclass[tikz,border=3mm]{standalone}

\usepackage{forest}
\usepackage[utf8]{inputenc}

\begin{document}

\begin{forest}
for tree={grow'=0, l=0, l sep=2em, 
         child anchor=west, anchor=west,  
          parent anchor=east, 
          tier/.pgfmath=level(),
          align=right,
          edge path={\noexpand\path[\forestoption{edge}](!u.parent anchor)|-(.child anchor)\forestoption{edge label};},
          }
[, calign=child,  calign child=2
    [Pressen
           [uniaxiales\\ Pressen]
            [isostatisches Pressen]
            [Vibrationspressen]
            [Stampfen]
        ]
        [Plastisches\\Formen
            [Extrudieren]
            [Drehen]
        ] 
        [Gießen 
            [Schlickergießen ]
            [Druckgießen ]
            [Spritzgießen ]
            [Foliengießen ]
]
    ]
\end{forest}
\end{document}

enter image description here

Best Answer

Explanation

Related Solutions

[Tex/LaTex] My version of Red-Black Tree

[Tex/LaTex] Text alignment and form of connectors (edges) in tikz tree

Related Question