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

Question

[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 находится у других объектов. Как сделать так, чтобы те объекты, у которых нет так сказать папы, кидать в отдельный массив?

Answer 1

[0xD34F]

const roots = arr.filter((n, i, a) => !a.some(m => m.id === n.root_id));

или

const roots = arr.filter(function(n) {
  return !this.has(n.root_id);
}, new Set(arr.map(n => n.id)));

Comments

[jizzy]

помогло, спасибо

Answer 2

[Дмитрий Беляев]

// проиндексируем по ключам
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 начнет впаривать факториальную сложность новичкам, а то с квадратичной веб конечно тормозит, но не такими темпами...