Укладка дерева

Дерево — планарный граф. Согласно следствию из формулы Эйлера: для дерева с [math]N[/math] вершинами [math]N - 1 \le 3 \cdot N - 6[/math].

Укладка дерева

Пример поуровневой укладки дерева

Существуют несколько способов укладки дерева на плоскости.

Поуровневая укладка

Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения, при котором вершины глубины [math]a[/math] имеют координату [math]y = – a[/math], а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми. Возможна реализация за линейное время, позволяющая получить оптимальное по ширине плоское дерево в области размера [math]O(N^2)[/math] (где [math]N[/math] — число вершин дерева).

Радиальная поуровневая укладка

Тот же граф, но уложенный радиально

Радиальная поуровневая укладка дерева отличается тем, что его уровни имеют вид концентрических окружностей, поддеревья занимают секторные сегменты.

Выбор угла [math]\beta_p[/math] секторного сегмента для поддерева с корнем [math]p[/math] и количеством вершин [math]l(p)[/math] определяется следующим образом: пусть вершина [math]p[/math] лежит на уровне [math]C_i[/math], тогда для каждого ее сына [math]q[/math] имеем: [math]\beta_q = \min(\frac{l(q)\beta_p}{l(p)}, \tau)[/math], где [math]\tau[/math] — это угол области [math]F_p[/math], определяемой пересечением касательной к точке [math]p[/math] уровня [math]C_i[/math] и окружностью уровня [math]C_{i+1}[/math].

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

Пример укладки двоичного дереве в виде hv-изображения

hv-изображения

При hv-изображении дерева для каждой вершины [math]p[/math] выполняются следующие свойства:

• сын вершины [math]p[/math] ставится в ряд за [math]p[/math] либо по горизонтали справа, либо по вертикали вниз;
• не пересекаются минимальные прямоугольники с горизонтальными и вертикальными вершинами, покрывающие поддеревья вершины [math]p[/math].