Código para los dos primeros casos.

Question

Estoy tratando de representar los AVL de una manera antigua que me enseñaron y que encontré más intuitiva de mostrar en comparación con la mayoría de los libros comunes hoy en día. Las imágenes sin procesar con las características que me interesan se muestran a continuación desde laLibro de Niklaus Wirth 1986y algunas notas escritas a mano.

Si bien la visualización puede ser específica, la representación de AVL es un concepto general de estructuras de datos de la informática y, en realidad, la intención es utilizar dichos dibujos para apuntes de conferencias. Por eso creo que puede ser útil para un público más amplio.

De este (el libro) estoy tratando de obtener exactamente lo que se muestra: Some nodes as circles, some as long vertical rectangles, con líneas discontinuas resaltando la parte inferior del árbol y un solo nodo con una X que indica el nodo de eliminación. Algunos rectángulos permanecen arriba, dentro y debajo como se muestra en la figura. He intentado representar las líneas discontinuas como una especie de nodo tikz y colocarlas en consecuencia, pero no tuve suerte.

---

A partir de las notas escritas a mano, estoy tratando de obtener numbers around the nodes (-2, -1, h-1, etc)las letras 'A,B,C,D' en los rectángulos y las circle oriented arrows to indicate rotation direction.

---

Pude encontrar formas de representar números alrededorotra preguntatambién trata de representarPartes del árbol con formas triangulares.pero modificar sus ejemplos mínimos a lo que quiero ha sido particularmente desafiante.

Answer 1

El basado en TikZforestpaqueteparece hacer el trabajo de manera relativamente eficiente. El siguiente ejemplo debería ayudarle a empezar.

Defino dos estilos de nodo,

• circnodeformatea un nodo como un círculo
• rectnode=<num>formatea un nodo como un rectángulo, con una altura igual a <num>x.5cm

Además, defino una macro \crossnodepara agregar un cuadro cruzado a una posición específica (en sus ejemplos, esto suele ser (some rectnode.south))

Por último, las dos líneas discontinuas se dibujan manualmente y se colocan en una capa de fondo.

Código para los dos primeros 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}

Producción