Задать вопрос
@jizzy

Как из массива, представляющего дерево, извлечь корни?

Есть массив объектов:

var array = [ 
        {
          "name": "test",
          "id": "1",
          "root_id": "33"
        },
        {
          "name": "test",
          "id": "2",
          "root_id": "33"
        },
        {
          "name": "test",
          "id": "70",
          "root_id": "90"
        },
        {
          "name": "test",
          "id": "55",
          "root_id": "90"
        },
        {
          "name": "test",
          "id": "33",
          "root_id": "55"
        },
]

У каждого есть root_id и этот айди как child находится у других объектов. Как сделать так, чтобы те объекты, у которых нет так сказать папы, кидать в отдельный массив?
  • Вопрос задан
  • 132 просмотра
Подписаться 1 Простой Комментировать
Решение пользователя Дмитрий Беляев К ответам на вопрос (2)
bingo347
@bingo347 Куратор тега JavaScript
Crazy on performance...
// проиндексируем по ключам
const [rootIndex, idIndex] = array.reduce(([roots, ids], obj) => {
  (roots[obj.root_id] ??= []).push(obj);
  ids[obj.id] = obj;
  return [roots, ids];
}, [{}, {}]);
// и найдем по нему нужные объекты:
const objectsWithoutExistingParent = Object.keys(rootIndex).filter(key => !idIndex.hasOwnProperty(key)).flatMap(key => rootIndex[key]);
console.log(objectsWithoutExistingParent);

Конечно чуть больше кода, чем у 0xD34F, зато с линейной сложностью
P.S. а я все жду, когда 0xD34F начнет впаривать факториальную сложность новичкам, а то с квадратичной веб конечно тормозит, но не такими темпами...
Ответ написан
Комментировать