HV або Про те, як непогано малювати бінарні дерева

Як-то давно хотілося чогось написати, але все вже було. А тут трапився випадок, та тим більше інтернет відразу нічого не видав…

Я хотів би сказати велике спасибі А. Дайняк за прочитаний курс і додати, що це лише виклад шматочка курсу, і на більше я не претендую.

Всюди у статті дерево = бінарне дерево

Дійсно неважко перетворювати маленькі дерева (напр. 5-10) аркушів. І для них можна використовувати природне уяву (яке типу ЛКП). І це виходить досить непогано.

Може бути навіть можна спробувати намалювати дерево з 100 вузлів. Але от якщо вузлів більше — наприклад 1000, то можна малювати дерева. Але от читати їх (і розуміти) буде зовсім незручно. Причому під читанням ми розуміємо саме зображення дерева на екрані, таке щоб їх просто не замазало нескінченно сильно, тобто в одне велике пляма.
image
Одним з варіантів боротьби з цим, але напевно навіть не скільки боротьби, а просто якийсь структури нормальної візуалізації — Horisontal Vertical-дерево. Тобто для візуалізації використовується от що:

  1. Ми гуляємо тільки в image. Хоча це зовсім необов'язково з точки зору реалізації. Просто так буде зручно нам.
  2. Нам би хотілося, щоб ми як-то вдало вигравали в площі і читаності. (Але розповідати про це зараз не хочеться, може бути тільки сказати, що суперузкая і довга смужка-дерево зовсім не читається.)
Так ось — концепція подання HV-tree проста (і рекурсивна): якщо у нас є 1 дерево і дерево 2 і ми хочемо об'єднати їх (тобто зробити поддеревьями одного і того ж дерева, то ось як буде робитися така операція:

Тобто як відбувається склеювання абсолютно формально:

1. У нас є задана довжина ребра (що, загалом-то, природно). І склеювати ми можемо за яким правилом. Що ми робимо:
Встаємо в корінь, S=0. Йдемо з кореня до всіх аркушів і кожен раз як йдемо вправо (від екрану) S=S+1.
2. Те ж саме з другим деревом.
3. Вниз ми закріплюємо дерево, яке ширше (у якого S більше). А праворуч — решта.
Якщо вони рівні нам не принципово як вішати (хоча, звісно, нам би краще довге вниз, якщо ми все-таки хочемо якось обмежувати малюнок, але якщо ми не обмежені у поданні варто спробувати зробити навпаки — бачити буде зручніше).

Ось саме так ми визначаємо такі дерева і процес побудови.

Ну і як приклад — порівняння подання в стд вигляді і HW-укладання.

  1. Неповне дерево в стд. поданні.
    image
  2. Повне дерево в стд. подання: Треба сказати, що ми не зможемо уявити все дерево ребрами однієї ширини. (А точніше — якщо ребро йде з сайту на n знизу рівні (лист — рівень 0, предлист — 1), то довжина ребра повинна бути n*s, де s-- одиничний ребро. (В моєму малюнку не відразу, тому що я посувають кути ребер.)
    image
  3. Перше дерево в HV-поданні. Це те ж дерево, що і на першій картинці.
    image


Ось. Таке подання, яке принцип читається дещо краще, ніж стандартне подання.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.