748
правок
Изменения
Нет описания правки
[[Файл:Layer-graph.jpg|250px|left|thumb|Рисунок 1. Пример поуровневой укладки дерева.]]
=== Поуровневая укладка ===
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения (''(англ. layered drawing)''), при котором вершины глубины <tex>a</tex> имеют координату <tex>y = – a</tex>, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми (см. рисунок 1). Возможна реализация за линейное время, позволяющая получить оптимальное по ширине [[Укладка графа на плоскости|плоское дерево]] в области размера <tex>O(N^2)</tex> (где <tex>N</tex> — число вершин дерева).
<br>
=== Радиальная поуровневая укладка ===
Радиальная поуровневая укладка(''(англ. radial drawing)'') дерева отличается тем, что его уровни имеют вид концентрических окружностей (см. рисунок 2).
Вершины глубины <tex>a</tex> располагаются на окружностях с радиусом <tex>r = a</tex>, при этом каждое поддерево находится внутри некоторого сектора (то есть между двумя лучами исходящими из центра).
Тогда <tex>\beta_q = \min(\frac{l(q)}{l(p)}\beta_p, \tau)</tex>, где <tex>\tau</tex> — это угол области <tex>F_p</tex>, определяемой пересечением касательной в точке <tex>p</tex> к окружности уровня <tex>i</tex> и окружностью уровня <tex>i+1</tex>. Угол <tex>\tau</tex> необходим для того, чтобы отрезок <tex>pq</tex> не пересек окружность уровня <tex>i</tex>.
Радиальное изображение дерева часто используют для представления свободных деревьев<ref name = "Свободное дерево">Под свободными деревьями(''(англ. free trees)'') понимают деревья без выделенного корня. </ref>, причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин <ref name="Центральная вершина">Центральная вершина {{---}} эта такая вершина, для которой расстояние от которой до самой удаленной вершины {{---}} минимальное среди всех вершин графа. Формально: Пусть <tex>r(p) = \underset{u:u\in V(G)}{\sup} dist(p, u)</tex>, тогда <tex>p</tex> {{---}} центральная, если <tex>r(p) = \underset{v:v\in V(G)}{\inf} r(v)</tex>. Понятно, что таких вершин может быть несколько. Под расстоянием здесь подразумевается длина кратчайшего пути.</ref>.
[[Файл:Hv_tree.jpg|250px|left|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]]
<br>
=== hv-изображения ===
Бинарные деревья<ref name = "Бинарное дерево">Бинарное дерево (двоичное дерево, ) ''(англ. binary tree)''), то есть такое дерево, у каждой вершины которого не более двух поддеревьев.</ref> можно изобразить при помощи hv-изображений (''(англ. horizontal-vertical drawing)'', (см. рисунок 3). При этом для каждой вершины <tex>p</tex> выполняются следующие свойства:
* сын вершины <tex>p</tex> ставится в ряд за <tex>p</tex> либо по горизонтали справа, либо по вертикали вниз
* два прямоугольника, ограничивающие левое и правое поддерево вершины <tex>p</tex> не пересекаются
