6

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.

Improve this question
2
  • Welcome to TeX.SX. Questions about how to draw specific graphics that just post an image of the desired result are really not reasonable questions to ask on the site. Instead of just describing how you modified code that from a different site, please post a minimal compilable document showing that you've tried to produce the image and then people will be happy to help you with any specific problems you may have. See minimal working example (MWE) for what needs to go into such a document.
    – Benedikt Bauer
    Apr 17, 2014 at 14:47
  • As you see, I provided an answer below, but after you edited your question, I am confused. You uploaded an image but then your description of the desired output seems not to follow that image. What exactly are you trying to achieve? If the image you posted doesn't correspond to the desired output, then please add a reaslistic image of the expected result.
    – Gonzalo Medina
    Apr 17, 2014 at 18:03

2 Answers 2

Reset to default
8

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.

Improve this answer
1
  • Thank you for nice solution (it fully fulfills my desire and it's also well commented so I'm able to understand what I need). I like that it is more automatic, than drawing rectangles around already build tree.
    – Bender250
    Apr 18, 2014 at 11:47
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.

enter image description here

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}
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.