Código para os dois primeiros casos

Question

Estou tentando representar os AVLs de uma forma antiga que aprendi e achei mais intuitiva de exibir em comparação com os livros mais comuns hoje em dia. As imagens brutas com os recursos nos quais estou interessado são mostradas abaixo noLivro de Niklaus Wirth de 1986e algumas notas escritas à mão.

Embora a visualização possa ser específica, representar AVLs é um conceito geral de estruturas de dados da ciência da computação, e a intenção é, na verdade, usar tais desenhos para notas de aula. Portanto, acredito que pode ser útil para um público mais amplo.

A partir deste (o livro) estou tentando obter exatamente o que é mostrado: Some nodes as circles, some as long vertical rectangles, com linhas tracejadas destacando a parte inferior da árvore e um único nó com um X indicando o nó de remoção. Alguns retângulos ficam acima, dentro e abaixo conforme mostrado na figura. Tenho tentado representar as linhas tracejadas como algum tipo de nó tikz e posicioná-las de acordo, mas sem sorte.

---

A partir das notas escritas à mão, estou tentando obter numbers around the nodes (-2, -1, h-1, etc)as letras 'A,B,C,D' nos retângulos e o circle oriented arrows to indicate rotation direction.

---

Consegui encontrar maneiras de representar números ao redoroutra perguntatambém tente representarpartes da árvore com formas triangularesmas modificar seus exemplos mínimos para o que desejo tem sido particularmente desafiador.

Answer 1

O baseado em TikZforestpacoteparece fazer o trabalho de forma relativamente eficiente. O exemplo a seguir deve ajudá-lo a começar.

Eu defino dois estilos de nó,

• circnodeformata um nó como um círculo
• rectnode=<num>formata um nó como um retângulo, com altura igual a <num>x.5cm

Além disso, defino uma macro \crossnodepara anexar uma caixa cruzada a uma posição especificada (nos seus exemplos, geralmente é (some rectnode.south))

Por último, as duas linhas tracejadas são desenhadas manualmente e colocadas em uma camada de fundo.

Código para os dois primeiros casos

\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}

Saída