# How to draw AVL rectangle represention in TikZ?

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.

-
It seems like you already have tried something, please provide what you have tried as a MWE. Currently it stands as a "do it for me question". – zeroth Dec 27 '13 at 12:46
It is. I saw and previously made questions of these types and they seem acceptable by this community. I did some search like I mentioned and the provided links both contain MWEs. If it is a problem now to make such requests I can spend some time trying to put something together, but my last "MWE" was not a MWE due to lack of expertise and had enough bad code to have someone reworking from scratch. Just let me know if it is a problem and I will update accordingly. thank you! – Oeufcoque Penteano Dec 27 '13 at 12:51
It is generally a good custom to provide a MWE, and it have always been the preferred way of asking questions on this site. However, often people will answer questions if they are "easy" or the answerer have tried it beforehand. If you get an answer it is not a problem, however, you will typically involve more people with your question by providing said MWE. Regards :) – zeroth Dec 27 '13 at 13:01
Thanks for the clarification! Yes, I would rather avoid trying an MWE since I am not too experienced with TikZ. If it seems too troublesome for others, I will try putting something together, but I do believe it will be more burdersome for someone trying to start from my code than from references I would be using for the code itself. – Oeufcoque Penteano Dec 27 '13 at 13:02

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

-
Thank you! This is amazing. I am having trouble finding the forest.sty on the link you provided. Any tips? I know how to install a .sty just lost on the fact they don't have one there and therefore I can't still compile the solution. – Oeufcoque Penteano Dec 27 '13 at 23:32
Let me reformulate the question: Installing them and generating the .sty file is fine ($latex forest.dtx) and ($latex forest.ins) does the trick. But many other files are generated on the process, are they supposed to go somewhere other than the .sty? – Oeufcoque Penteano Dec 28 '13 at 0:16
I am adding here for reference of others who want to replicate fully what I asked: You can find on page 9 of the documentation (mirror.hmc.edu/ctan/graphics/pgf/contrib/forest/forest.pdf) how to add tikz code embedded on forest. The following extra code adds a rotation arrow (use mathabx,graphicx package for it to work): {\draw node[node distance=0.6cm,right of=E, align=center]{h-1};} {\draw node[node distance=1cm,below of=E, align=center]{D};} {\draw node[node distance=0.6cm,right of=B, align=center] {$\circlearrowright$};} There might be a more simpler way but it works. – Oeufcoque Penteano Dec 28 '13 at 1:28
@OeufcoquePenteano: I used MikTeX's package manager to install forest. Please consult en.wikibooks.org/wiki/LaTeX/Installing_Extra_Packages if you want to manually install missing packages in your local TeX distro. I usually discard the files generated from the manual installation process. One of those files (most likely forest.pdf) is the package documentation, and it should be put in texmf/doc folder. – Herr K. Dec 28 '13 at 4:08