☰

绘制递归树

tag-icon • tag-icon tikz-pgf forest recursion
绘制递归树

假设我们要T(n)=T(n/4)+T(n/2)+n^2使用这里介绍的 Justtree 包绘制递归树（justtree.sty）。

我尝试如下：

    \begin{justtree}
    {
        declare count={tree n}{1},
        just format={xshift=1.5em},
        annotate/.style={% style should be applied to the rightmost node at each level for which an arrow and annotation is required
            if n children=0{}{
                right just=$n^2$,
            },
        },
        where n children=0{
            edge={dotted},
        }{},
        for tree={
            math content,
            if level=0{}{%
                if level=1{%
                    tree n'=1,
                }{%
                    if n=1{%
                        tree n/.wrap pgfmath arg={#1}{tree_n("!u")},
                    }{%
                        tree n/.wrap pgfmath arg={#1}{int((tree_n("!u"))},
                    },
                },
            },
            delay={
                if level=1{
                    content=n^2,
                    tikz+={
                        \draw [<->] (!F.south west) +(-2.5em,0) coordinate (c) -- (.north -| c) node [midway, anchor=south, sloped] {$\log_{\frac{4}{3}}n$};
                    }
                    ,
                }{
                    if n children=0{%
                    }{
                        if level=0{}{
                            content/.wrap 2 pgfmath args={(\frac{#1n}{#2})^2}{(tree_n()==1) ? "" : (tree_n())}{int(4^(level("!u")))},
                        }
                    }
                }
            },
        },
    }
    [, annotate
    [
    [
    [[][]]
    [[][]]
    ]
    [
    [[][]]
    [[][]]
    ]
    ]
    [, annotate
    [
    [[][]]
    [[][]]
    ]
    [, annotate
    [, annotate[][]]
    [[][]]
    ]
    ]
    ]
\end{justtree}

不幸的是，上面的代码绘制了一个递归树，T(n)=T(n/4)+T(3n/4)+n^2 有人可以帮我修改上面的代码来实现我的目标吗？

答案1

注 1：我不认为我应该回答这个问题。它提供了一段没有链接或归属的复制代码，没有努力去改编该代码，甚至懒得解释新树应该是什么样子。我回答是因为我喜欢用 Forest 做事。如果有人觉得它有用，那就太好了。

注 2：我认为justtrees它本身就有缺陷，几年前就放弃了。与 不同prooftrees，justtrees它早早夭折了，从未进入 CTAN。我没有计划让它复活。我建议forest直接使用，除非你正在绘制画面，在这种情况下我建议prooftrees。如果这个答案与那个立场相矛盾，那么这个答案就更糟了。

买者自负 ...

递归树

这个例子比前面的例子简单得多，因为分子总是n。（但我花了一些时间才弄清楚，因为我必须先弄清楚递归树是什么。）

\documentclass[border=10pt]{standalone}
\usepackage[linguistics]{forest}
\usepackage{justtrees}

\begin{document}
\begin{justtree}
  {% ateb cfr: https://tex.stackexchange.com/a/702157/
    declare count={tree n}{1},
    just format={xshift=1.5em},
    annotate/.style={% style should be applied to the rightmost node at each level for which an arrow and annotation is required
      if n children=0{}{
        right just=$#1$,
      },
    },
    where n children=0{
      edge={dotted},
    }{},
    for tree={
      math content,
      if level=0{}{%
        if level=1{%
          tree n'=1,
        }{%
          if n=1{%
            tree n/.process={ O+nw+P {!u.tree n} {int(4*#1)}},
          }{%
            tree n/.process={ O+nw+P {!u.tree n} {int(2*#1)}},
          },
        },
      },
      delay={
        if level=1{
          content=n^2,
          tikz+={
            \draw [<->] (!F.south west) +(-2.5em,0) coordinate (c) -- (.north -| c) ;
          }
          ,
        }{
          if n children=0{%
          }{
            if level=0{}{
              content/.process={%
                O  w
                {tree n}  {(\frac{n}{#1})^2}
              },
            }
          }
        }
      },
    },
  }
  [, annotate=n^2
    [
      [
        [[][]]
        [[][]]
      ]
      [
        [[][]]
        [[][]]
      ]
    ]
    [, annotate=\frac{5n^2}{16}
      [
        [[][]]
        [[][]]
      ]
      [
        [[][]]
        [[][]]
      ]
    ]
  ]
\end{justtree}

\end{document}

相关内容