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

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 = [];
for (const n of arr) {
  if (!arr.some(m => m.id === n.root_id)) {
    roots.push(n);
  }
}

// или

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

// или

const roots = (function get(i = 0, n = arr[i]) {
  return n
    ? [].concat(arr.every(m => m.id !== n.root_id) ? n : [], get(-~i))
    : []
})();

Но вообще, дерево-то можно и собрать, результатом как раз будет массив искомых объектов (конечно, не без дополнения в виде вложенных массивов):

function createTree({
  data,
  key = 'id',
  parentKey = 'parentId',
  childrenKey = 'children',
}) {
  const tree = Object.fromEntries(data.map(n => [
    n[key],
    { ...n, [childrenKey]: [] },
  ]));

  return Object.values(tree).filter(n => (
    !tree[n[parentKey]]?.[childrenKey].push(n)
  ));
}


const tree = createTree({
  data: arr,
  parentKey: 'root_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 начнет впаривать факториальную сложность новичкам, а то с квадратичной веб конечно тормозит, но не такими темпами...