Дерево (Tree): d3.tree() и d3.cluster()

Иерархические структуры данных являются базовой моделью для визуализации отношений «родитель—потомок» в графах, файловых системах, организационных схемах и многих других предметных областях. В визуализации таких структур ключевую роль играют алгоритмы компоновки деревьев, среди которых в D3.js используются два основных подхода: d3.tree() и d3.cluster().

Обе функции строят иерархические макеты на основе данных, предварительно преобразованных в формат d3.hierarchy. Несмотря на схожесть математической модели, поведение и геометрия результирующих структур существенно различаются.

Перед применением любого иерархического layout данные приводятся к структуре HierarchyNode. Это ключевой этап, без которого tree и cluster не могут работать.

Основная форма исходных данных:

const data = {
  name: "root",
  children: [
    { name: "A" },
    {
      name: "B",
      children: [
        { name: "B1" },
        { name: "B2" }
      ]
    }
  ]
};

Преобразование:

const root = d3.hierarchy(data);

После этого каждый узел получает дополнительные свойства:

  • depth — уровень вложенности
  • height — высота поддерева
  • parent — ссылка на родителя
  • children — массив дочерних узлов

Эти данные становятся основой для вычисления координат.

Алгоритмическая основа layout-деревьев

И d3.tree(), и d3.cluster() используют один и тот же принцип: разделение пространства по уровням глубины (depth) и распределение узлов по оси, перпендикулярной направлению роста дерева.

Основная идея:

  • Одна ось фиксирует глубину (обычно вертикаль или радиус)
  • Вторая ось распределяет узлы внутри уровня

Различие заключается в стратегии распределения ширины.

d3.tree(): равномерное распределение потомков

d3.tree() строит классическое «дерево» с равномерным распределением узлов по горизонтали (или окружности в радиальной версии).

Поведение

  • Все листья распределяются равномерно
  • Поддеревья занимают пропорциональную ширину
  • Учитывается плотность ветвей
  • Минимизируется пересечение ребер

Базовая инициализация

const treeLayout = d3.tree()
  .size([height, width]);

или для фиксированной глубины:

const treeLayout = d3.tree()
  .nodeSize([dx, dy]);

Отличительная особенность

tree() стремится к компактному размещению, где расстояние между листьями может варьироваться в зависимости от структуры поддерева.

Геометрия d3.tree()

После вызова:

treeLayout(root);

каждый узел получает координаты:

  • x — позиция по вертикали (или углу в радиальном режиме)
  • y — позиция по горизонтали (или радиусу)

Пример использования:

root.descendants().forEach(d => {
  console.log(d.x, d.y);
});

В классическом вертикальном дереве:

  • x — вертикальная координата
  • y — горизонтальная глубина

d3.cluster(): выравнивание листьев

d3.cluster() является модификацией дерева, в которой все листья выравниваются по одной линии.

Ключевая идея

В отличие от tree(), где пространство распределяется с учётом поддеревьев, cluster():

  • фиксирует одинаковые расстояния между всеми листьями
  • выравнивает конечные узлы на одном уровне
  • игнорирует «вес» поддеревьев при распределении ширины

Инициализация cluster

const clusterLayout = d3.cluster()
  .size([height, width]);

или:

const clusterLayout = d3.cluster()
  .nodeSize([dx, dy]);

Геометрия d3.cluster()

После вычисления:

clusterLayout(root);

структура координат аналогична tree():

  • x — позиция по основной оси
  • y — глубина

Однако распределение по оси X отличается принципиально: листья образуют равномерную «линейку».

Сравнение tree и cluster

1. Распределение узлов

  • d3.tree() Учитывает структуру поддеревьев, создавая адаптивную плотность

  • d3.cluster() Выравнивает листья независимо от структуры

2. Визуальная структура

  • tree():

    • асимметричные поддеревья
    • плотные участки при большом числе потомков
    • более «естественное» дерево

  • cluster():

    • строгая симметрия
    • выровненные конечные узлы
    • более «диаграммная» структура

3. Области применения

d3.tree()

  • файловые системы
  • организационные структуры
  • decision trees
  • представление реальной иерархии

d3.cluster()

  • таксономии
  • филогенетические деревья
  • схемы классификации
  • визуальные каталоги

Параметры конфигурации

Обе функции поддерживают одинаковый набор базовых методов настройки.

size()

Определяет область распределения:

d3.tree().size([height, width]);
d3.cluster().size([height, width]);

Используется при необходимости полного заполнения контейнера.

nodeSize()

Альтернатива фиксированного шага между узлами:

d3.tree().nodeSize([dx, dy]);

Особенности:

  • dx — вертикальный шаг
  • dy — горизонтальный шаг
  • игнорирует размеры контейнера

separation()

Функция управления расстоянием между узлами:

treeLayout.separation((a, b) => {
  return a.parent === b.parent ? 1 : 2;
});

Логика:

  • узлы одного родителя могут быть ближе
  • узлы разных поддеревьев раздвигаются

В cluster() эта функция особенно важна, так как структура выравнивания жестче.

Радиальные деревья

Обе модели могут быть развернуты в полярную систему координат.

После расчёта координат:

const radialPoint = (d) => {
  const angle = d.x;
  const radius = d.y;
  return [
    radius * Math.cos(angle - Math.PI / 2),
    radius * Math.sin(angle - Math.PI / 2)
  ];
};

Применение:

  • tree() даёт неравномерное радиальное дерево
  • cluster() формирует аккуратные круговые уровни

После расчёта layout строятся рёбра:

const links = root.links();

Каждая связь:

{
  source: Node,
  target: Node
}

Генерация пути:

d3.linkHorizontal()

или для радиального дерева:

d3.linkRadial()

Влияние структуры данных на результат

Даже при одинаковых настройках tree() и cluster() реагируют на форму входных данных по-разному.

Глубокие цепочки

A → B → C → D
  • оба алгоритма дают почти идентичный результат

Широкие поддеревья

A
├── B1
├── B2
├── B3
├── B4
  • tree() сжимает ветви с учётом структуры
  • cluster() выравнивает B1–B4 на одной линии

Несбалансированные деревья

A
├── B
│   └── C
│       └── D
└── E
  • tree() визуально отражает глубину цепочки
  • cluster() выравнивает E и D по одной горизонтали

Оптимизация визуального пространства

В больших иерархиях выбор между tree() и cluster() напрямую влияет на читаемость.

tree()

  • лучше подходит при ограниченной ширине
  • снижает перекрытия в глубоких структурах
  • адаптивно использует пространство

cluster()

  • лучше подходит при большом числе листьев
  • улучшает сравнение конечных узлов
  • упрощает визуальное восприятие классификаций

Поведение при масштабировании

При изменении размеров контейнера:

  • size() требует перерасчёта layout
  • nodeSize() сохраняет стабильную геометрию

В интерактивных интерфейсах чаще используется nodeSize, так как:

  • узлы не «прыгают»
  • структура остаётся стабильной при zoom/pan

Особенности вычислительной модели

Алгоритм внутри обеих функций основан на рекурсивном обходе дерева с вычислением:

  • предварительных позиций листьев
  • агрегированных размеров поддеревьев
  • оптимального распределения координат

Различие заключается в постобработке:

  • tree() корректирует позиции с учётом «веса» поддеревьев
  • cluster() игнорирует веса и фиксирует шаг между листьями

Комбинации с другими компонентами D3

Обе функции часто используются совместно с:

  • d3.scaleLinear — масштабирование координат
  • d3.drag — интерактивное перемещение узлов
  • d3.zoom — навигация по дереву
  • d3.transition — анимация перестроения layout

Пример анимации:

node.transition()
  .duration(500)
  .attr("transform", d => `translate(${d.y},${d.x})`);

Итоговая логика выбора layout

  • структура отражает реальную иерархию с неравномерной вложенностью → tree()
  • структура представляет классификацию или равномерные категории → cluster()
  • при необходимости строгого выравнивания листьев → cluster()
  • при необходимости сохранения топологической выразительности → tree()
Оглавление