- PVSM.RU - https://www.pvsm.ru -
Как-то давно хотелось чего-то написать, но всё уж было. А тут представился случай, да тем более интернет сразу ничего не выдал…
Я хотел бы сказать большое спасибо А. Дайняк за прочитанный курс и добавить, что это лишь изложение кусочка курса, и на большее я не претендую.
Всюду в статье дерево = бинарное дерево
Действительно нетрудно отрисовывать маленькие деревья (напр. 5-10) листов. И для них можно использовать естественное представление (которое типа ЛКП). И это получается довольно неплохо.
Может быть даже можно попробовать нарисовать дерево из 100 узлов. Но вот если узлов больше — например 1000, то можно рисовать деревья. Но вот читать их (и понимать) будет совсем неудобно. Причём под чтением мы понимаем именно изображение дерева на экране, такое чтобы их просто не замазало бесконечно сильно, т.е. в одно большое пятно.
Одним из вариантов борьбы с этим, но наверно даже не сколько борьбы, а просто какой-то структуры нормальной визуализации — Horisontal Vertical-дерево. То есть для визуализации используется вот что:
Так вот — концепция представления HV-tree проста (и рекурсивна): если у нас есть дерево 1 и дерево 2 и мы хотим объединить их (т.е. сделать поддеревьями одного и того же дерева, то вот как будет делаться такая операция:
То есть как происходит склейка совершенно формально:
1. У нас есть заданная длина ребра (что в общем-то естественно). И склеивать мы можем во по какому правилу. Что мы делаем:
Встаём в корень, S=0. Идём из корня до всех листов и каждый раз как идём вправо (от экрана) S=S+1.
2. То же самое со вторым деревом.
3. Вниз мы закрепляем дерево, которое шире (у которого S больше). А вправо — оставшееся.
Если они равны — нам не принципиально как вешать (хотя конечно нам бы лучше длинное вниз, если мы всё-таки хотим как-то ограничивать рисунок, но если мы не ограничены в представлении — стоит попробовать сделать наоборот — видеть будет удобнее).
Вот именно так мы определяем такие деревья и процесс и построения.
Ну и в качестве примера — сравнение представления в стд виде и HW-укладке.
Вот. Такое вот представление, которое в принцип читается несколько лучше, чем стандартное представление.
Автор: Zhe_Ver
Источник [1]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/graficheskij-dizajn/212101
Ссылки в тексте:
[1] Источник: https://habrahabr.ru/post/315718/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.