Как реализовать «якорную» привязку узла (setAsRoot) при клике, чтобы всё дерево перестраивалось относительно выбранного человека?
Реализация «якорной» привязки узла (setAsRoot) — это распространённая задача при работе с деревьями, графами и визуализацией иерархических данных (например, генеалогических деревьев, оргструктур, социальных графов). Суть операции: при клике на узел он становится новым корнем, и всё дерево перестраивается так, чтобы выбранный элемент оказался на вершине иерархии.
## Алгоритм перестройки дерева (re-rooting)
Классический алгоритм смены корня работает следующим образом:
1. **Найти путь от старого корня до нового узла.** Обходим дерево (DFS или BFS), запоминая родителей каждого узла.
2. **Инвертировать рёбра вдоль пути.** Для каждого узла на пути от нового корня к старому корню меняем направление связи «родитель → дочерний» на обратное.
3. **Обновить ссылки.** Новый корень теряет родителя (parent = null), а его бывший родитель становится его дочерним узлом.
## Пример реализации на JavaScript
javascript
function setAsRoot(nodeId, nodes, edges) {
// Строим карту смежности
const parentMap = {};
edges.forEach(edge => {
parentMap[edge.target] = edge.source;
});
// Находим путь от nodeId до текущего корня
const path = [];
let current = nodeId;
while (current !== undefined) {
path.push(current);
current = parentMap[current];
}
// Инвертируем рёбра вдоль пути
const newEdges = […edges];
for (let i = 0; i e.source === parent && e.target === child
);
if (edgeIndex !== -1) {
newEdges[edgeIndex] = { source: child, target: parent };
}
}
return { nodes, edges: newEdges, root: nodeId };
}
## Обработка клика в UI
javascript
node.on(‘click’, function(event, d) {
const result = setAsRoot(d.id, treeData.nodes, treeData.edges);
treeData = result;
renderTree(treeData); // перерисовываем дерево
});
## Важные нюансы
— **Анимация переходов:** при перестройке дерева рекомендуется использовать плавные переходы (например, `d3.transition()`), чтобы пользователь понимал, что произошло.
— **История навигации:** сохраняйте стек предыдущих корней, чтобы реализовать кнопку «Назад».
— **Производительность:** для больших деревьев (тысячи узлов) используйте виртуализацию или ленивую загрузку дочерних узлов.
— **Визуальное выделение:** новый корень стоит визуально выделять (цветом, размером, иконкой), чтобы пользователь всегда понимал текущую «точку отсчёта».
— **Сохранение состояния:** при работе с генеалогическими деревьями важно сохранять выбранный корень в URL или localStorage для возможности поделиться ссылкой.
Таким образом, операция setAsRoot требует грамотного обхода графа, инверсии рёбер и обновления визуализации, что делает её мощным инструментом навигации по иерархическим данным.