Zhe_Ver Nov 21 2016 at 08:15

HV или О том, как неплохо отрисовывать бинарные деревья

2 min

7.7K

Graphic design*Computer Animation*

From sandbox

+17

Comments 10

jced Nov 21 2016 at 08:42

А что если рассмотреть вариант увеличения угла между ребрами, длина которых увеличивается? Для того, чтобы немного уменьшить вертикальный размер. Или это ухудшает читаемость?

Zhe_Ver Nov 21 2016 at 08:43

Если вы всё-таки угол имеете в виду, то тогда получится уже не HV-представление. HV-представление имеет только 2 угла: 0 и Pi/2.

Peter_Voronov Nov 21 2016 at 10:18

А вот если немного менять угол каждого следующего потомка. Допустим от 20 до 80 градусов, и этот диапазон делить между требуемым количеством колен. Не ради сужения размера графика, а именно ради информативности. Тогда в любой точке будет понятно, какого порядка потомок и примерно сколько шагов до корня.

Zhe_Ver Nov 22 2016 at 23:53

Я не могу так сходу прикинуть, но над этим можно порассуждать. Если это действительно интересно — давайте пообсуждаем какие-то идеи в личных сообщениях. Может и до статейки доиграемся)

Saffron Nov 21 2016 at 12:37

А если это тернарное дерево, то можно вспомнить про гиперболическую плоскость.

third112 Nov 21 2016 at 14:25

тем более интернет сразу ничего не выдал…

М.б. не так искали? Гугл на запрос «визуализация дерева» кидает много ссылок. Можно еще в Википедии посмотреть: там большой список источников и софта для визуализации графов, что-то может быть полезным для бинарных деревьев. Из сравнительно старых источников:

Н. Вирт, Алгоритмы+структуры данных=программы, М., Мир, 1985, С. 267 — Изображение древовидной структуры. Там исходный код программы для распечатки бинарного дерева на алфавитно-цифровом (не графическом) принтере.

В.Н.Касьянов, В.А.Евстигнеев, Графы в программировании: обработка, визуализация и применение, СПб, БХВ-Петербург, 2003, С.357. — Рисование деревьев.

Вопрос по статье: а как предлагается нумеровать/метить вершины (узлы)? (ИМХО без меток рисунок будет не очень информативным).

Zhe_Ver Nov 21 2016 at 22:41

Не совсем понял вопрос про нумерацию… Вроде же алгоритм однозначно говорит как выводить, нет?

Может и выдаёт, но на слова HW-tree не отзывался.

third112 Nov 22 2016 at 05:13

Я о том где и как рисовать метки (цифры и/или буквы)? На вершинах? рядом? А если рядом с вершиной, то нужно чтобы соседние метки не пересекались.

Deosis Nov 22 2016 at 04:07

Судя по изображению, вы просто повернули изображение дерева набок. (представьте египетскую пирамиду в таком положении)
Для многих привычно видеть корень вверху в центре, как раз на месте правого ребенка в HV дереве.
Ещё стандартное представление дерева легко расширяется на тернарные и В-деревья. Как их можно нарисовать в вашем представлении?

Zhe_Ver Nov 22 2016 at 23:50

1. Нет, не просто набок. Присмотритесь. По крайней мере, так может быть получилось только из-за какой-то случайной симметрии.
2. О представлении B-деревьях вообще стоит говорить отдельно. Я могу написать статью, в которой будут кое-какие идеи о представлениях, если это имеет смысл.