Code für die ersten beiden Fälle

Question

Ich versuche, AVLs auf eine alte Art und Weise darzustellen, die mir beigebracht wurde und die ich im Vergleich zu den meisten gängigen Büchern heutzutage intuitiver zu gestalten fand. Die Rohbilder mit den Merkmalen, die mich interessieren, sind unten zu sehen aus demNiklaus Wirth 1986 Buchund einige handschriftliche Notizen.

Während die Visualisierung spezifisch sein kann, ist die Darstellung von AVLs ein allgemeines Datenstrukturkonzept der Informatik, und die Absicht besteht eigentlich darin, solche Zeichnungen für Vorlesungsnotizen zu verwenden. Daher glaube ich, dass es für ein breiteres Publikum nützlich sein kann.

Aus diesem (dem Buch) versuche ich, genau das zu bekommen, was gezeigt wird: Some nodes as circles, some as long vertical rectangles, mit gestrichelten Linien, die den unteren Teil des Baums hervorheben, und einem einzelnen Knoten mit einem X, der den zu entfernenden Knoten anzeigt. Einige Rechtecke bleiben darüber, innerhalb und darunter, wie in der Abbildung gezeigt. Ich habe versucht, die gestrichelten Linien als eine Art Tikz-Knoten darzustellen und entsprechend zu positionieren, aber ohne Erfolg.

---

Aus den handschriftlichen Notizen versuche ich numbers around the nodes (-2, -1, h-1, etc), die Buchstaben „A, B, C, D“ auf den Rechtecken und die circle oriented arrows to indicate rotation direction… herauszuarbeiten.

---

Ich konnte Wege finden, Zahlen darzustellen, umeine andere Frageversuchen Sie auch darzustellenTeile des Baumes mit DreiecksformenAber es war eine besondere Herausforderung, ihre Minimalbeispiele meinen Wünschen entsprechend anzupassen.

Answer 1

Das TikZ-basierteforestPaketscheint die Aufgabe relativ effizient zu erledigen. Das folgende Beispiel soll Ihnen den Einstieg erleichtern.

Ich definiere zwei Knotenstile,

• circnodeformatiert einen Knoten als Kreis
• rectnode=<num>formatiert einen Knoten als Rechteck mit einer Höhe von <num>x.5cm

Außerdem definiere ich ein Makro \crossnodezum Anhängen eines durchgestrichenen Kästchens an eine bestimmte Position (in Ihren Beispielen ist dies normalerweise (some rectnode.south)).

Zuletzt werden die beiden gestrichelten Linien manuell gezeichnet und auf eine Hintergrundebene gelegt.

Code für die ersten beiden Fälle

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

Ausgabe