Укладка дерева — различия между версиями
(→hv-изображения) |
(→Радиальная поуровневая укладка) |
||
| Строка 24: | Строка 24: | ||
Радиальное изображение дерева часто используют для представления свободных деревьев<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 = "Свободное дерево">Под свободными деревьями ''(англ. 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>. | ||
| − | |||
<br> | <br> | ||
<br> | <br> | ||
| Строка 31: | Строка 30: | ||
[[Файл:Hv_tree.jpg|250px|right|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]] | [[Файл:Hv_tree.jpg|250px|right|thumb|Рисунок 3. Пример укладки двоичного дереве в виде hv-изображения.]] | ||
| + | |||
=== hv-изображения === | === hv-изображения === | ||
Версия 16:45, 13 января 2016
Дерево — планарный граф. Его планарность можно подтвердить, предъявив способ укладки для произвольного дерева. По формуле Эйлера: .
Содержание
Укладка дерева
Существуют несколько способов укладки дерева на плоскости.
Поуровневая укладка
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения (англ. layered drawing), при котором вершины глубины имеют координату , а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми (см. рисунок 1). Возможна реализация за линейное время, позволяющая получить оптимальное по ширине плоское дерево в области размера (где — число вершин дерева).
Радиальная поуровневая укладка
Радиальная поуровневая укладка (англ. radial drawing) дерева отличается тем, что его уровни имеют вид концентрических окружностей (см. рисунок 2).
Вершины глубины располагаются на окружностях с радиусом , при этом каждое поддерево находится внутри некоторого сектора (то есть между двумя лучами исходящими из центра). Определим способ выбора угла этого сектора для некоторого поддерева вершины находящейся на уровне . Пусть угол сектора для дерева с корнем равен . Пусть корень поддерева(непосредственный ребенок ) — вершина , обозначим количество вершин в дереве с корнем как . Тогда , где — это угол области , определяемой пересечением касательной в точке к окружности уровня и окружностью уровня . Угол необходим для того, чтобы отрезок не пересек окружность уровня .
Радиальное изображение дерева часто используют для представления свободных деревьев[1], причем в качестве вершины, размещаемой в центре, берется одна из его центральных вершин [2].
hv-изображения
Бинарные деревья[3] можно изобразить при помощи hv-изображений (англ. horizontal-vertical drawing) (см. рисунок 3). При этом для каждой вершины выполняются следующие свойства:
- сын вершины ставится в ряд за либо по горизонтали справа, либо по вертикали вниз
- два прямоугольника, ограничивающие левое и правое поддерево вершины не пересекаются
Примечания
- ↑ Под свободными деревьями (англ. free trees) понимают деревья без выделенного корня.
- ↑ Центральная вершина — эта такая вершина, для которой расстояние от которой до самой удаленной вершины — минимальное среди всех вершин графа. Формально: Пусть , тогда — центральная, если . Понятно, что таких вершин может быть несколько. Под расстоянием здесь подразумевается длина кратчайшего пути.
- ↑ Бинарное дерево (двоичное дерево) (англ. binary tree), то есть такое дерево, у каждой вершины которого не более двух поддеревьев.
