Я хотел бы сказать большое спасибо А. Дайняк за прочитанный курс и добавить, что это лишь изложение кусочка курса, и на большее я не претендую.
Всюду в статье дерево = бинарное дерево
Действительно нетрудно отрисовывать маленькие деревья (напр. 5-10) листов. И для них можно использовать естественное представление (которое типа ЛКП). И это получается довольно неплохо.
Может быть даже можно попробовать нарисовать дерево из 100 узлов. Но вот если узлов больше — например 1000, то можно рисовать деревья. Но вот читать их (и понимать) будет совсем неудобно. Причём под чтением мы понимаем именно изображение дерева на экране, такое чтобы их просто не замазало бесконечно сильно, т.е. в одно большое пятно.
Одним из вариантов борьбы с этим, но наверно даже не сколько борьбы, а просто какой-то структуры нормальной визуализации — Horisontal Vertical-дерево. То есть для визуализации используется вот что:
- Мы гуляем только в
. Хотя это совершенно необязательно с точки зрения реализации. Просто так будет удобно нам. - Нам бы хотелось чтобы мы как-то удачно выигрывали в площади и читаемости. (Но рассказывать об этом сейчас не хочется, может быть только сказать, что суперузкая и длинная полоска-дерево совсем не читается.)
Так вот — концепция представления HV-tree проста (и рекурсивна): если у нас есть дерево 1 и дерево 2 и мы хотим объединить их (т.е. сделать поддеревьями одного и того же дерева, то вот как будет делаться такая операция:
То есть как происходит склейка совершенно формально:
1. У нас есть заданная длина ребра (что в общем-то естественно). И склеивать мы можем во по какому правилу. Что мы делаем:
Встаём в корень, S=0. Идём из корня до всех листов и каждый раз как идём вправо (от экрана) S=S+1.
2. То же самое со вторым деревом.
3. Вниз мы закрепляем дерево, которое шире (у которого S больше). А вправо — оставшееся.
Если они равны — нам не принципиально как вешать (хотя конечно нам бы лучше длинное вниз, если мы всё-таки хотим как-то ограничивать рисунок, но если мы не ограничены в представлении — стоит попробовать сделать наоборот — видеть будет удобнее).
Вот именно так мы определяем такие деревья и процесс и построения.
Ну и в качестве примера — сравнение представления в стд виде и HW-укладке.
- Неполное дерево в стд. представлении.
- Полное дерево в стд. представлении: Надо сказать, что мы не сумеем представить всё дерево рёбрами одной ширины. (А точнее — если ребро идёт из узла на n снизу уровне (лист — уровень 0, предлист — 1), то длина ребра должна бы быть n*s, где s-- единичное ребро. (В моём рисунке не сразу так, потому что я подвигал углы рёбер.)
- Первое дерево в HV-представлении. Это то же дерево, что и на первой картинке.
Вот. Такое вот представление, которое в принцип читается несколько лучше, чем стандартное представление.
Комментарии (10)
Peter_Voronov
21.11.2016 13:18
А вот если немного менять угол каждого следующего потомка. Допустим от 20 до 80 градусов, и этот диапазон делить между требуемым количеством колен. Не ради сужения размера графика, а именно ради информативности. Тогда в любой точке будет понятно, какого порядка потомок и примерно сколько шагов до корня.Zhe_Ver
23.11.2016 02:53Я не могу так сходу прикинуть, но над этим можно порассуждать. Если это действительно интересно — давайте пообсуждаем какие-то идеи в личных сообщениях. Может и до статейки доиграемся)
Saffron
21.11.2016 15:37А если это тернарное дерево, то можно вспомнить про гиперболическую плоскость.
third112
21.11.2016 17:25тем более интернет сразу ничего не выдал…
М.б. не так искали? Гугл на запрос «визуализация дерева» кидает много ссылок. Можно еще в Википедии посмотреть: там большой список источников и софта для визуализации графов, что-то может быть полезным для бинарных деревьев. Из сравнительно старых источников:
Н. Вирт, Алгоритмы+структуры данных=программы, М., Мир, 1985, С. 267 — Изображение древовидной структуры. Там исходный код программы для распечатки бинарного дерева на алфавитно-цифровом (не графическом) принтере.
В.Н.Касьянов, В.А.Евстигнеев, Графы в программировании: обработка, визуализация и применение, СПб, БХВ-Петербург, 2003, С.357. — Рисование деревьев.
Вопрос по статье: а как предлагается нумеровать/метить вершины (узлы)? (ИМХО без меток рисунок будет не очень информативным).Zhe_Ver
22.11.2016 01:41Не совсем понял вопрос про нумерацию… Вроде же алгоритм однозначно говорит как выводить, нет?
Может и выдаёт, но на слова HW-tree не отзывался.third112
22.11.2016 08:13Я о том где и как рисовать метки (цифры и/или буквы)? На вершинах? рядом? А если рядом с вершиной, то нужно чтобы соседние метки не пересекались.
Deosis
22.11.2016 07:07Судя по изображению, вы просто повернули изображение дерева набок. (представьте египетскую пирамиду в таком положении)
Для многих привычно видеть корень вверху в центре, как раз на месте правого ребенка в HV дереве.
Ещё стандартное представление дерева легко расширяется на тернарные и В-деревья. Как их можно нарисовать в вашем представлении?Zhe_Ver
23.11.2016 02:501. Нет, не просто набок. Присмотритесь. По крайней мере, так может быть получилось только из-за какой-то случайной симметрии.
2. О представлении B-деревьях вообще стоит говорить отдельно. Я могу написать статью, в которой будут кое-какие идеи о представлениях, если это имеет смысл.
jced
А что если рассмотреть вариант увеличения угла между ребрами, длина которых увеличивается? Для того, чтобы немного уменьшить вертикальный размер. Или это ухудшает читаемость?
Zhe_Ver
Если вы всё-таки угол имеете в виду, то тогда получится уже не HV-представление. HV-представление имеет только 2 угла: 0 и Pi/2.