How to draw AVL rectangle represention in TikZ?

Question

I am trying to represent AVL's in an old way that I was taught and found more intuitive to display in comparison to most common books nowadays. The raw images with the features I am interested in are shown below from the Niklaus Wirth 1986 book and some hand written notes.

While the visualization may be specific, representing AVLs is a general data structures concept of computer science, and the intention is actually to use such drawings for lecture notes. So I believe it can be useful to a wider audience.

From this one (the book) I am trying to get exactly what it is shown: Some nodes as circles, some as long vertical rectangles, with dashed lines highlighting the bottom part of the tree, and one single node with an X indicating the node of removal. Some rectangles stay above, within and below as shown in the figure. I have been trying to try representing the dashed lines as some sort of tikz node and position accordingly but no luck.

---

From the hand written notes, I am trying to get numbers around the nodes (-2, -1, h-1, etc), letters 'A,B,C,D' on the rectangles, and the circle oriented arrows to indicate rotation direction.

---

I was able to find ways to represent numbers around another question as well try to represent parts of the tree with triangle shapes but modifying their minimal examples to what I want has been particularly challenging.

Answer 1

The TikZ-based forest package seems to do the job relatively efficiently. The following example should get you started.

I define two node styles,

• circnode formats a node as a circle
• rectnode=<num> formats a node as a rectangle, with height equal to <num> x .5cm

Moreover, I define a macro \crossnode for appending a crossed box to a specified position (in your examples, this is usually (some rectnode.south))

Lastly, the two dashed lines are manually drawn and put on a background layer.

Code for first two cases

\documentclass{article}
\usepackage{forest}
\usetikzlibrary{backgrounds}


\forestset{
  circnode/.style={circle,draw,minimum size=.5cm,inner sep=0},
  rectnode/.style={draw,minimum width=.5cm,fill=white,minimum height=#1*.5cm,child anchor=north,anchor=north},
}
\newcommand\crossnode[2][anchor=north]{
  \node(temp)[draw,fill=white,minimum size=.5cm,yshift=\pgflinewidth,#1]at(#2){};
  \draw(temp.north west)--(temp.south east) (temp.north east)--(temp.south west);
}

\begin{document}
\begin{forest}
  for tree={l+=.5cm,s sep=1cm},
  [
    [B,circnode
      [A,circnode
        [,rectnode=3,name=n][,rectnode=3]
      ]
      [,rectnode=3]
    ]
  ]
  \crossnode[anchor=north]{n.south}
  \begin{scope}[on background layer]
    \draw[dashed,thin] let \p1=(temp.north), \p2=(current bounding box.west), \p3=(current bounding box.east) in
    (\x2-.5cm,\y1)--(\x3+.5cm,\y1) (\x2-.5cm,\y1+.5cm)--(\x3+.5cm,\y1+.5cm);
  \end{scope}
\end{forest}

\begin{forest}
  for tree={l+=.5cm,s sep=1cm},
  [
    [C,circnode
      [A,circnode,
        [,rectnode=3]
        [B,circnode
          [,rectnode=2,name=n1]
          [,rectnode=2,name=n2]
        ]
      ]
      [,rectnode=3]
    ]
  ]
  \crossnode{n1.south}
  \crossnode{n2.south}
  \begin{scope}[on background layer]
    \draw[dashed,thin] let \p1=(temp.north), \p2=(current bounding box.west), \p3=(current bounding box.east) in
    (\x2-.5cm,\y1)--(\x3+.5cm,\y1) (\x2-.5cm,\y1+.5cm)--(\x3+.5cm,\y1+.5cm);
  \end{scope}
\end{forest}
\end{document}

Output