Преобразование плоского JSON в древовидную структуру в JS

Быстрый ответ

Мы сталкиваемся с задачей трансформации линейного массива в древовидную структуру. Основной алгоритм состоит в создании словаря (отображения), соединяющего идентификаторы узлов и их позиции в массиве, что обеспечивает быстрый поиск. Далее проводится вложенная обработка массива для распределения каждого элемента в список потомков соответствующего родителя. Элементы, у которых не указан parent_id, будут рассматриваться как корневые узлы дерева.

Вот так выглядит пример кода:

function buildTree(items) {
    let map = {}, node, roots = [], i;
    for (i = 0; i < items.length; i++) {
        map[items[i].id] = i; // сохраняем связь между id элемента и его индексом
        items[i].children = []; // начинаем формировать список потомков
    }
    for (i = 0; i < items.length; i++) {
        node = items[i];
        if (node.parent_id) {
            // если указан родитель, помещаем элемент в его потомков
            items[map[node.parent_id]].children.push(node);
        } else {
            // в противном случае это корневой узел
            roots.push(node);
        }
    }
    return roots;
}

const items = [
    { id: 1, name: 'Root1', parent_id: null },
    { id: 2, name: 'Child1', parent_id: 1 },
    { id: 3, name: 'Child2', parent_id: 1 }
];

console.log(buildTree(items));

Данный пример эффективно строит многоуровневую иерархию, формируя из массива готовую древовидную структуру.

Повышение эффективности и управление специальными случаями

Работу с большими объемами данных облегчает высокая производительность алгоритма. В нашем случае, алгоритм имеет временную сложность Θ(n log(n)), что обеспечивает повышенную эффективность при росте объема данных. Но что делать с небольшими массивами? Тут будет полезна рекурсивная фильтрация. Важно инициализировать карту и список потомков до итерации по массиву — не тратите драгоценное время разработчика без нужды!

Помимо этого, стоит обратить внимание на элементы, у которых указаны несуществующие parent_id. Такие "подвешенные ветви", узлы без корня, требуют корректировки, чтобы не выпасть из структуры дерева.

Рассмотрение альтернативных решений

Рекурсивный подход

Для обработки меньших массивов можно использовать более простой рекурсивный подход:

function unflatten(array, parent_id = null) {
    return array
        .filter(item => item.parent_id === parent_id)
        .map(item => ({ ...item, children: unflatten(array, item.id) }));
}

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

Обработка нескольких корневых узлов

Если у вас есть несколько корневых элементов, они все должны быть учтены:

items.filter(item => item.parent_id === null).forEach(rootNode => roots.push(rootNode));

Проверка и валидация данных

Не забудьте провести проверку данных на корректность. Например, обработайте ситуации, когда parent_id отсутствует в массиве:

if (node.parent_id && !map[node.parent_id]) {
    console.warn(`Родительский ID (${node.parent_id}) не найден для узла с ID (${node.id}). У нас проблема.`);
}

Современный JavaScript и его возможности

Использование оператора расширения из ES6 значительно упрощает чтение кода и делает его кратким. Объект Map повысит эффективность поиска элементов:

const itemMap = new Map(items.map(item => [item.id, { ...item, children: [] }]));

Визуализация

Давайте визуализируем процесс:

Исходный массив: [ребёнок, родитель, бабушка или дедушка]

Функция преобразования: связываем детей с родителями, а родителей – с бабушками или дедушками.

Получаем иерархическую структуру в виде дерева:

          [ бабушка или дедушка ]
                 /     \
         [ родитель ] [ дядя или тётя ]
               /
        [ ребёнок ]

В итоге имеем наглядную и структурированную древовидную структуру.

Стремление к аутономности решения

Да, можно использовать библиотеки вроде underscore.js или lodash, однако наша цель — индивидуальность решения. Решение, которое не зависит от сторонних библиотек, является самодостаточным и понятным.

В погоне за производительностью

Словосочетание "Big O" — это не только красиво звучит, но и позволяет оценить производительность кода. Для работы с большими массивами рекомендуется применять оператор цикла for вместо forEach для увеличения скорости исполнения. И не забывайте тестировать ваш код на различных данных.

Полезные материалы

1. Работа с объектами – JavaScript | MDN
2. Визуализация структур данных и алгоритмов – VisuAlgo
3. Структуры данных: Бинарное дерево – YouTube
4. JSFiddle – Онлайн-песочница для эспериментов с кодом
5. Дерево (структура данных) – Википедия
6. Как понять рекурсию в JavaScript