☰

如何创建具有级别标签和工作标签的递归树？

tag-icon • tag-icon forest
如何创建具有级别标签和工作标签的递归树？

我正在尝试创建递归树来解决递归的时间复杂度问题。这是我迄今为止的尝试，但标签全都乱了，我似乎无法让工作标签正常工作。

\begin{forest}
for tree={
    draw,
    minimum size=0.5cm,
    s sep=1cm,
    fit=band,
},
[{$n^2$}, name=level0
    [{$\left(\frac{n}{2}\right)^2$}, name=level1
        [{$\left(\frac{n}{4}\right)^2$}, name=level2
            [{$\vdots$}, name=vdots1
                [{$\left(\frac{n}{2^i}\right)^2$}, name=leveli
                    [{$\vdots$}, name=vdots2
                        [{1}, name=base]
                    ]
                ]
            ]
        ]
        [{$\left(\frac{n}{4}\right)^2$}]
        [{$\left(\frac{n}{4}\right)^2$}]
    ]
    [{$\left(\frac{n}{2}\right)^2$}]
    [{$\left(\frac{n}{2}\right)^2$}]
]
\node [anchor=west] at ([xshift=2cm]level0.east) {Level 0: $n^2$};
\node [anchor=west] at ([xshift=2cm]level1.east) {Level 1: $\frac{3n^2}{4}$};
\node [anchor=west] at ([xshift=2cm]level2.east) {Level 2: $\frac{9n^2}{16}$};
\node [anchor=west] at ([xshift=2cm]leveli.east) {Level i: $\frac{3^i n^2}{4^i}$};
\node [anchor=west] at ([xshift=2cm]base.east) {Base: $1$};
\end{forest}

我想要的效果如下：在此处输入图片描述

我怎样才能做到这一点？

答案1

使用相对位置坦克-|。下面的代码片段需要知道哪些是最左边和最右边的节点。

\documentclass[tikz]{standalone}
\usepackage{forest}
\usetikzlibrary{positioning}
\begin{document}
  \begin{forest}
    for tree={
      draw,
      minimum size=0.5cm,
      s sep=1cm,
      fit=band,
    },
    [{$n^2$}, name=level0
    [{$\left(\frac{n}{2}\right)^2$}, name=level1
    [{$\left(\frac{n}{4}\right)^2$}, name=level2
    [{$\vdots$}, name=vdots1
    [{$\left(\frac{n}{2^i}\right)^2$}, name=leveli
    [{$\vdots$}, name=vdots2
    [{1}, name=base]
    ]
    ]
    ]
    ]
    [{$\left(\frac{n}{4}\right)^2$}]
    [{$\left(\frac{n}{4}\right)^2$}]
    ]
    [{$\left(\frac{n}{2}\right)^2$}]
    [{$\left(\frac{n}{2}\right)^2$},name=level1_3]
    ]
    \node (label0) [anchor=east, xshift=-1cm] at (level0-|leveli) {$0$};
    \node (wd0) [anchor=west, xshift=1cm] at (level0-|level1_3) {$n^2$};
    \node [above=2em of label0, font=\bfseries] {Level};
    \node [above=2em of wd0, font=\bfseries] {Work done};
    \node at (level1-|label0) {$1$};
    \node at (level1-|wd0) {$\frac{3n^2}{4}$};
    \node at (level2-|label0) {$2$};
    \node at (level2-|wd0) {$\frac{9n^2}{16}$};
    \node at (leveli-|label0) {$i$};
    \node at (leveli-|wd0) {$\frac{3^in^2}{4^i}$};
    \node at (base-|label0) {$\log_2n$};
    \node at (base-|wd0) {$3^{\log_2n}$};
  \end{forest}
\end{document}

在此处输入图片描述

答案2

您可以将其设为具有根节点的单个forest节点phantom。

笔记：

  • tier/.pgfmath=level()协调所有级别
  • math content当你的节点（大部分）以数学模式排​​版时很有用

在此处输入图片描述

\documentclass{article}
\usepackage{forest}
\tikzset{mydots/.style={thick, dotted}}
\begin{document}
    \begin{forest}
        for tree={if level=1{font=\bfseries}{math content}, tier/.pgfmath=level(), fit=band, s sep=1cm}
        [, phantom
            [Level[0, for tree={no edge}[1[2[\vdots[i[\vdots[\log_2n]]]]]]]]
            [[n^2, no edge, draw
                [\left(\frac{n}{2}\right)^2, draw
                    [\left(\frac{n}{4}\right)^2, draw
                        [, coordinate, for tree={edge=mydots}[\left(\frac{n}{2^i}\right)^2, draw[, coordinate[1, draw]]]]
                    ]
                    [\left(\frac{n}{4}\right)^2, draw]
                    [\left(\frac{n}{4}\right)^2, draw]
                ]
                [\left(\frac{n}{2}\right)^2, draw[, edge=mydots]]
                [\left(\frac{n}{2}\right)^2, draw[, edge=mydots]]]]
            [Work done[0, for tree={no edge}[n^2, for tree={no edge}[\frac{3n^2}{4}[\vdots[\frac{3^i n^2}{4^i}[\vdots[1]]]]]]]
        ]]
    \end{forest}
\end{document}

答案3

Sandy G 的出色答案的半自动化版本。仍然需要[]在幻影根周围添加内容节点，但Level和Work Done标签会自动添加，并且大部分格式由样式处理recurrence tree。创建节点的内容也相对简单forest，但我认为这不太可能有用，因为不需要构建相同的树。整体风格，，recurrence tree可以用来格式化具有不同内容但相同一般结构的树。（但如果您确实想要，有许多答案显示了如何自动生成这样的树。）

请注意，比版本tier/.option=level快一点，比版本快。很棒，但速度很慢。由于自动化无论如何都会增加编译时间，因此此代码的编译时间仍将比 Sandy G 的代码更长。.pgfmaths sep'=1cms sep=1cmpgfmath

\documentclass{standalone}
\usepackage{forest}
% ateb: https://tex.stackexchange.com/a/709595/ addaswyd o ateb Sandy G: https://tex.stackexchange.com/a/709482/
\tikzset{mydots/.style={thick, dotted}}
\forestset{%
  recurrence tree/.style={%
    for root={phantom},
    for tree={%
      math content,
      tier/.option=level, 
      fit=band, 
      s sep'=1cm,
    },
    delay={%
      for nodewalk={fake=r,1}{replace by={[Level,font=\bfseries,delay=append]}},
      delay n=1{% delay={} doesn't work here but delay n=1{} does?
        for nodewalk={fake=r,3}{replace by={[Work Done,font=\bfseries,delay=append]}},
      },
      delay n=3{do dynamics},
    },
    before typesetting nodes={%
      for nodewalk={r,1,tree,fake=r,3,tree}{%
        no edge,
        if content={}{coordinate}{},
      },
      for nodewalk={fake=r,2,tree}{%
        if content={}{coordinate}{draw},
        if={%
          > Ow+P {n children}{isodd(#1)}
        }{%
          calign=child edge,
          calign primary child/.process={Ow+n{n children}{(#1+1)/2}},
        }{},
      },
    },    
  },
}
\begin{document}
\begin{forest}
  recurrence tree,
  [
    [0
        [1
          [2 [\vdots [i [\vdots[\log_2n] ] ] ]
          ]
        ]
    ]
    [n^2, no edge
      [\left(\frac{n}{2}\right)^2
        [\left(\frac{n}{4}\right)^2
            [, 
              for tree={edge=mydots},
                [\left(\frac{n}{2^i}\right)^2
                  [
                    [1]
                  ]
                ]
            ]
        ]
        [\left(\frac{n}{4}\right)^2]
        [\left(\frac{n}{4}\right)^2]
      ]
      [\left(\frac{n}{2}\right)^2
        [, edge=mydots]
      ]
      [\left(\frac{n}{2}\right)^2
        [, edge=mydots]
      ]
    ]
    [0
      [n^2, 
        [\frac{3n^2}{4} [\vdots [\frac{3^i n^2}{4^i} [\vdots [1] ] ] ]
        ]
      ]
    ]
  ]
\end{forest}
\end{document}

输出应该与原始代码的结果相同：

自动化树的结果

相关内容