☰

如何在 tikz 中将合并的红黑树绘制成 2,3,4 树？

tag-icon • tag-icon tikz-trees trees
如何在 tikz 中将合并的红黑树绘制成 2,3,4 树？

我在学习材料中使用tikz，我想展示 RB 树和 B 树（2、3、4 树）之间的相似性。我希望我的输出看起来类似于维基百科中的这个示例。 将 RB 树合并到 B 树

对于 RB 树，我使用的设置几乎与http://www.texample.net/tikz/examples/red-black-tree/（只是零节点的设置不同）。我可以在同一层创建 3 个节点，但它会使用手动设置的位置。我也不知道如何将这些节点放在矩形中。

有人能给我提示或解决方案吗？我将不胜感激。

编辑：我尝试过这个：

    \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}

输出如下：我的解决方案是使用固定位置 我至少需要一个矩形作为合并节点的边框。如果您还知道如何插入一些分隔符（在同一层的箭头下），那就更好了。

//我希望，现在的帖子符合有关问题的规则，并对之前的版本表示歉意。

答案1

由于树的每个“节点”除了标签之外，几乎所有内容都是常量，因此这里非常适合应用pic（需要 PGF/TikZ 3.0.0 版本）；有关更多详细信息，请参阅第节18 张图片：路径上的小图片pgf 手册。

代码（下面有一些解释性说明）：

\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}

结果：

在此处输入图片描述

解释

pic按以下方式使用语法

\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} 
    }
  }
}

允许你使用\pic（或\path pic ...）绘制以下形式的每个“节点”

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

最后一个参数（示例中为“box1”）只是 中使用的拟合节点的名称，因此pic您可以使用该名称放置其他元素；此名称还用于为构成每张图片的三个圆形节点中的每一个命名。在每个 中\pic，每个圆形节点在内部都命名为<name>-left、<name>-middle和<name>-right，其中<name>是第四个参数。

例如，使用

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

将产生

在此处输入图片描述

这里，拟合节点（灰色填充矩形）被指定名称box1；标记为“12”的圆形节点为box1-left，标记为“5”的圆形节点为box1-middle，标记为“8”的圆形节点为box1-rught。

答案2

另一种尝试是通过Tikz tree。除了 OP 的样式定义之外，此解决方案还添加了一种line样式，以便于绘制矩形框。

在此处输入图片描述

代码

\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}

相关内容