在 TiKZ 的搜索树中添加级别和平衡

Question

我有以下 AVL 搜索树：

\documentclass[border=10pt]{standalone}
  \usepackage{tikz}
   \begin{document}
    \begin{tikzpicture}[
                > = stealth, % arrow head style
                shorten > = 1pt, % don't touch arrow head to node
                auto,
                node distance = 4cm, % distance between nodes
                semithick % line style
            ]

            \tikzstyle{every state}=[
                draw = black,
                thin,
                fill = blue!50!,
                minimum size = 2mm
            ]


            \node[state] (b){};
             \node[state] (f)[below left=1cm and 1.5cm of b] {};
               \node[state] (g)[below left=1cm and 0.5cm of f] {};
               \node[state] (g2)[below right=1cm and 0.5cm of g] {};
               \node[state] (f2)[below right=1cm and 0.5cm of f] {};
            \node[state] (c)[below right=1cm and 1.5cm of b] {};
            \node[state] (d)[below right=1cm and 0.5cm of c] {};
             \node[state] (d2)[below left=1cm and 0.5cm of c] {};
              \node[state] (d3)[below right=1cm and 0.5cm of d2] {};
               \node[state] (d5)[below left=1cm and 0.5cm of d3] {};
               \node[state] (d4)[below left=1cm and 0.5cm of d2] {};
             \node[state] (h)[below right=1cm and 0.5cm of d] {};



              \path[-] (b) edge node {} (c);
              \path[-] (b) edge node {} (f);
                \path[-] (c) edge node {} (d);
               \path[-] (d) edge node {} (h);
                \path[-] (f) edge node {} (g);
                 \path[-] (f) edge node {} (f2);
                 \path[-] (c) edge node {} (d2);
                 \path[-] (d2) edge node {} (d3);
                 \path[-] (d2) edge node {} (d4);
                 \path[-] (d3) edge node {} (d5);
                   \path[-] (g) edge node {} (g2);


       \end{tikzpicture}
\end{document}

我想写下搜索树的 lovel 以及每个节点的余额，如下所示：

Answer 1

这是一个使用 Forest 的示例。标记级别很简单。标记节点几乎可以自动化，但我不知道“平衡”取决于什么。因此，这里没有自动化。相反，我通过标记根作为示例来展示如何手动标记节点。

\documentclass[tikz,border=10pt]{standalone}
\usepackage{forest}
\begin{document}
\begin{forest}
  for tree={
    draw, 
    circle,
    inner sep=1.5pt,
    fill=pink!75!black!20,
    l sep'+=2.5mm, 
    s sep'+=3.5mm,
  },
  before drawing tree={
    tikz+={
      \coordinate (a) at (current bounding box.east);
    },
    for nodewalk={
      r,
      while nodewalk valid={l}{l}
    }{
      tikz+/.process={
        Ow {level}{
          \node [anchor=west, font=\sffamily, magenta] at (.center -| a) {#1};
        }
      }
    }
  }
  [, label={[blue!50!cyan, font=\sffamily]right:1}
    [
      [
        [, phantom]
        []
      ]
      []
    ]
    [
      [
        []
        [
          []
          [, phantom]
        ]
      ]
      [
        [, phantom]
        [
          [, phantom]
          []
        ]
      ]
    ]
  ]
\end{forest}
\end{document}