Якось давно хотілося чогось написати, але все вже було. А тут представився випадок, та тим більше інтернет відразу нічого не видав...
Я хотів би сказати велике спасибі А.Дайняку за прочитаний курс і додати, що це лише виклад шматочка курсу, і на більше я не претендую.
Усюди у статті дерево = бінарне дерево
Дійсно неважко відмальовувати маленькі дерева (наприклад, 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-виставі. Це те ж дерево, що і на першій картинці.
Ось. Таке ось уявлення, яке в принцип читається дещо краще, ніж стандартне уявлення.