Изменения

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

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

Выбор Вершины глубины <tex>a</tex> располагаются на окружностях с радиусом <tex>r = a</tex>, при этом каждое поддерево находится внутри некоторого сектора (то есть между двумя лучами исходящими из центра). Определим способ выбора угла этого сектора для некоторого поддерева вершины <tex>p</tex> находящейся на уровне <tex>\beta_pi</tex> секторного сегмента . Пусть угол сектора для поддерева дерева с корнем <tex>p</tex> равен <tex>\beta_p</tex>. Пусть корень поддерева(и количеством вершин непосредственный ребенок <tex>l(p)</tex> определяется следующим образом: пусть ) - вершина <tex>pq</tex> лежит на уровне , обозначим количество вершин в дереве с корнем <tex>C_iq</tex>, тогда для каждого ее сына как <tex>l(q)</tex> имеем: .Тогда <tex>\beta_q = \min(\frac{l(q)\beta_p}{l(p)}\beta_p, \tau)</tex>, где <tex>\tau</tex> — это угол области <tex>F_p</tex>, определяемой пересечением касательной к точке окружности уровня <tex>pi</tex> уровня в точке <tex>C_ip</tex> и окружностью уровня <tex>C_{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>.

Бинарные деревья <ref name = "Бинарное дерево">Бинарное дерево (двоичное дерево, ''binary tree''), то есть такое дерево, у каждой вершины которого не более двух поддеревьев.</ref> можно изобразить при помощи hv-изображений (''horizontal-vertical drawing'', см. рисунок 3). При этом для каждой вершины <tex>p</tex> выполняются следующие свойства: