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

Материал из Викиконспекты
Перейти к: навигация, поиск

Дерево — планарный граф. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По формуле Эйлера: [math]V - E + F = 2, V - (V - 1) + F = 2 [/math] [math] \Leftrightarrow[/math][math] F = 1 [/math]. Значит дерево можно уложить на плоскость и у него будет только одна грань. Для произвольных графов есть гамма-алгоритм, который проверяет произвольный граф на планарность.

Укладка дерева[править]

Рисунок 1. Пример поуровневой укладки дерева.

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

Поуровневая укладка[править]

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





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

Рисунок 2. Граф из рисунка 1, но уложенный радиально.

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

Вершины глубины [math]a[/math] располагаются на окружностях с радиусом [math]r = a[/math], при этом каждое поддерево находится внутри некоторого сектора (то есть между двумя лучами исходящими из центра). Определим способ выбора угла этого сектора для некоторого поддерева вершины [math]p[/math] находящейся на уровне [math]i[/math]. Пусть угол сектора для дерева с корнем [math]p[/math] равен [math]\beta_p[/math]. Пусть корень поддерева(непосредственный ребенок [math]p[/math]) — вершина [math]q[/math], обозначим количество вершин в дереве с корнем [math]q[/math] как [math]l(q)[/math]. Тогда [math]\beta_q = \min\left(\dfrac{l(q)}{l(p)}\beta_p, \tau\right)[/math], где [math]\tau[/math] — это угол области [math]F_p[/math], определяемой пересечением касательной в точке [math]p[/math] к окружности уровня [math]i[/math] и окружностью уровня [math]i+1[/math]. Угол [math]\tau[/math] необходим для того, чтобы отрезок [math]pq[/math] не пересек окружность уровня [math]i[/math].

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



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

hv-изображения[править]

Бинарные деревья можно изобразить при помощи hv-изображений (англ. horizontal-vertical drawing) (см. рисунок 3). При этом для каждой вершины [math]p[/math] выполняются следующие свойства: сын вершины [math]p[/math] ставится в ряд за [math]p[/math]: либо по горизонтали справа, либо по вертикали вниз; два прямоугольника, ограничивающие левое и правое поддерево вершины [math]p[/math], не пересекаются.





См. также[править]

Примечания[править]

  1. Под свободными деревьями (англ. free trees) понимают деревья без выделенного корня.

Источники информации[править]