Код для первых двух случаев

Question

Я пытаюсь представить AVL старым способом, которому меня научили, и который я нашел более интуитивным для отображения по сравнению с большинством обычных книг в настоящее время. Необработанные изображения с интересующими меня функциями показаны ниже изНиклаус Вирт 1986 книгаи несколько рукописных заметок.

Хотя визуализация может быть специфичной, представление AVLs является общей концепцией структур данных в компьютерной науке, и намерение на самом деле состоит в том, чтобы использовать такие рисунки для лекционных заметок. Поэтому я считаю, что это может быть полезно для более широкой аудитории.

Из этой (книги) я пытаюсь получить именно то, что показано: Some nodes as circles, some as long vertical rectangles, с пунктирными линиями, выделяющими нижнюю часть дерева, и одним единственным узлом с X, указывающим на узел удаления. Некоторые прямоугольники остаются сверху, внутри и снизу, как показано на рисунке. Я пытался попытаться представить пунктирные линии как своего рода узел tikz и расположить соответствующим образом, но безуспешно.

---

Из рукописных заметок я пытаюсь извлечь numbers around the nodes (-2, -1, h-1, etc)буквы «A,B,C,D» на прямоугольниках и circle oriented arrows to indicate rotation direction.

---

Я смог найти способы представления чисел вокругДругой вопроса также попытаться представитьчасти дерева с треугольными формамино изменение их минимальных примеров в соответствии с моими пожеланиями оказалось особенно сложной задачей.

Answer 1

Основанный на TikZforestупаковкакажется, делает работу относительно эффективно. Следующий пример должен помочь вам начать.

Я определяю два стиля узлов,

• circnodeформатирует узел как круг
• rectnode=<num>форматирует узел как прямоугольник с высотой, равной <num>x.5cm

Более того, я определяю макрос \crossnodeдля добавления перечеркнутого поля в указанную позицию (в ваших примерах это обычно (some rectnode.south))

Наконец, вручную рисуются две пунктирные линии и наносятся на фоновый слой.

Код для первых двух случаев

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

Выход