0

I'm trying to create the following tree with tikz-tree, but don't how to add the arrow that indicates height. Please help.

Tree

Thank you!

  • I think you should show the community a little effort. – Dr. Manuel Kuehner Nov 17 '15 at 19:28
  • Post the code for the tree and somebody will surely be happy to show how to add the arrow. – cfr Nov 18 '15 at 3:57
3

This solution uses an experimental package, justtrees, based on forest. More specifically, it uses version 0.5. Please ask if you wish to use it. I am really using questions here to test it, but I can provide the code to the foolhardy. (An older version is around here somewhere but won't suffice for this example.)

One key advantage of forest is the conciseness with which trees may be specified in the source. justtrees is a wrapper for forest designed to support easy annotations to the left and right of the tree.

The justtree environment takes one mandatory argument. This may be empty. Otherwise it specifies the preamble for the tree and may be used to customise the contents and formatting.

\begin{justtree}
  {
    <preamble, if required>
  }
  <tree specification in forest's bracket notation>
\end{justtree}

A basic introduction to forest and instructions for specifying trees using its bracket notation are provided in the second part of my answer to a general tree-drawing question.

The actual specification for the tree in this case is simply this:

  [, annotate
    [
      [
        [[]]
      ]
      [
        [[]]
      ]
      [
        [[]]
      ]
    ]
    [
      [
        [[]]
      ]
      [
        [[]]
      ]
      [
        [[]]
      ]
    ]
    [, annotate
      [
        [[]]
      ]
      [
        [[]]
      ]
      [, annotate
        [[, annotate]]
      ]
    ]
  ]

The preamble for the tree does most of the work.

Shift annotations right to make room for the arrows:

    just format={xshift=1.5em},

Create a style, annotate for levels which should have annotations and arrows:

    annotate/.style={% style should be applied to the rightmost node at each level for which an arrow and annotation is required
      if level=1{% first level of tree (apparent root - the real root is added automatically at level 0)
        right just=$cn^2$,
      }{
        if n children=0{% terminal nodes
          right just=$\Theta(n^{\log_43})$
        }{% other nodes (if annotated)
          right just/.wrap pgfmath arg={$(\frac{3}{16})^##1cn^##1$}{level()},
        },
      },
      tikz+/.wrap pgfmath arg={\draw [->] (.east) -- (right just ##1.west);}{level()},
    },

For terminal nodes, we change the level distance for the node and its parent, use a dotted edge for the node and no edge for the parent:

    where n children=0{
      !u.no edge,
      !u.l sep-=10pt,
      l sep-=5pt,
      edge={dotted},
    }{},

Make the contents of all nodes within the tree use maths mode:

    for tree={
      math content,

Specify the content of nodes in the tree and draw the arrow at the left and the curly bracket at the bottom:

      delay={
        if level=1{
          content=cn^2,
          tikz+={
            \draw [<->] (!F.south west) +(-2.5em,0) coordinate (c) -- (.north -| c) node [midway, fill=white] {$\log_4n$};
            \draw [decorate, decoration={brace, mirror}] (!F.south west) -- (!L.south east) node [midway, below] {$n^{\log_43}$};
          },
        }{
          if n children=0{% terminal nodes have different content
            content=T(1),
            delay={% their parents have no content - delay this so it overwrites the specification below
              !u.content=,
            }
          }{% non-terminal nodes
            if level=0{}{% which are not at level 0 (the real root, automatically added by the justtree style)
              content/.wrap pgfmath arg={c(\frac{n}{#1})^2}{int(4^(level("!u")))},
            }
          }
        }
      },
    },
  }

The result with justtrees.sty looks like this:

just a tree, really

Code:

\documentclass[tikz,border=10pt]{standalone}
\usepackage{justtrees}% version 0.5
\usetikzlibrary{decorations.pathreplacing}
\begin{document}
\begin{justtree}
  {
    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 level=1{
        right just=$cn^2$,
      }{
        if n children=0{
          right just=$\Theta(n^{\log_43})$
        }{
          right just/.wrap pgfmath arg={$(\frac{3}{16})^##1cn^##1$}{level()},
        },
      },
      tikz+/.wrap pgfmath arg={\draw [->] (.east) -- (right just ##1.west);}{level()},
    },
    where n children=0{
      !u.no edge,
      !u.l sep-=10pt,
      l sep-=5pt,
      edge={dotted},
    }{},
    for tree={
      math content,
      delay={
        if level=1{
          content=cn^2,
          tikz+={
            \draw [<->] (!F.south west) +(-2.5em,0) coordinate (c) -- (.north -| c) node [midway, fill=white] {$\log_4n$};
            \draw [decorate, decoration={brace, mirror}] (!F.south west) -- (!L.south east) node [midway, below] {$n^{\log_43}$};
          },
        }{
          if n children=0{
            content=T(1),
            delay={
              !u.content=,
            }
          }{
            if level=0{}{
              content/.wrap pgfmath arg={c(\frac{n}{#1})^2}{int(4^(level("!u")))},
            }
          }
        }
      },
    },
  }
  [, annotate
    [
      [
        [[]]
      ]
      [
        [[]]
      ]
      [
        [[]]
      ]
    ]
    [
      [
        [[]]
      ]
      [
        [[]]
      ]
      [
        [[]]
      ]
    ]
    [, annotate
      [
        [[]]
      ]
      [
        [[]]
      ]
      [, annotate
        [[, annotate]]
      ]
    ]
  ]
\end{justtree}
\end{document}

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.