문제 개요
실무에서는 하나의 배열 안에 일대다(1:N) 관계로 얽힌 데이터를 다루는 경우가 많습니다. 예를 들어 조직도처럼 데이터가 레벨(level)을 기준으로 계층화되어 있고, 각 요소의 부모는 항상 자신보다 한 단계 위 레벨에 위치하며 parentId 속성으로 참조되는 구조입니다.
이렇게 평면(flat)하게 나열된 배열에서 다단계 트리 구조의 배열을 추출해야 한다면 어떻게 해야 할까요? 목표는 가장 높은 레벨의 요소들이 메인 배열을 구성하고, 그 자식 요소들은 각 부모의 children 서브 배열에 배치되는 형태를 만드는 것입니다.
입력 배열이 다음과 같이 주어졌다고 가정해 보겠습니다.
const arr = [
{ _id: 100, level: 3, parentId: null },
{ _id: 101, level: 2, parentId: 100 },
{ _id: 102, level: 2, parentId: 100 },
{ _id: 103, level: 2, parentId: 100 },
{ _id: 104, level: 1, parentId: 101 },
{ _id: 105, level: 1, parentId: 102 },
{ _id: 106, level: 1, parentId: 101 },
{ _id: 107, level: 1, parentId: 103 },
{ _id: 108, level: 1, parentId: 102 },
{ _id: 109, level: 1, parentId: 103 }
];이때 우리가 얻고자 하는 최종 구조는 다음과 같은 트리 형태입니다.
100
|
---------------------------------
| | |
101 102 103
------- ------ -------
| | | | | |
104 106 105 108 107 109예제 코드
이를 구현한 코드는 다음과 같습니다.
const prepareTree = (arr = [], root = null) => {
let res;
const obj = Object.create(null);
arr.forEach(el => {
el.children = obj[el._id] && obj[el._id].children;
obj[el._id] = el;
if (el.parentId === root) {
res = el;
} else {
obj[el.parentId] = obj[el.parentId] || {};
obj[el.parentId].children = obj[el.parentId].children || [];
obj[el.parentId].children.push(el);
}
});
return res;
};
console.log(JSON.stringify(prepareTree(arr), undefined, 4));코드 동작 방식
prepareTree 함수는 프로토타입 체인이 없는 순수 객체(Object.create(null))를 해시 맵처럼 활용해 배열을 단 한 번만 순회하면서(O(n)) 전체 트리를 완성합니다. 핵심 로직을 정리하면 다음과 같습니다.
- 순회 중 각 요소를
_id를 키로 하여 맵(obj)에 등록합니다. - 같은
_id에 이미 children이 할당되어 있다면 그 참조를 그대로 이어받아, 자식이 부모보다 먼저 나타나는 경우에도 데이터가 유실되지 않습니다. parentId가 루트 기준값(null)과 일치하는 요소는 결과 트리의 최상위 노드가 됩니다.- 나머지 요소는 부모 객체를 찾아(없으면 빈 객체를 생성한 뒤) 부모의
children배열에 추가합니다.
이 방식의 가장 큰 장점은 입력 배열의 순서에 의존하지 않는다는 점입니다. 또한 재귀 호출 없이 반복문 한 번으로 처리되기 때문에, 계층이 아주 깊은 대용량 데이터에서도 스택 오버플로우 걱정 없이 안정적으로 동작합니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
{
"_id": 100,
"level": 3,
"parentId": null,
"children": [
{
"_id": 101,
"level": 2,
"parentId": 100,
"children": [
{ "_id": 104, "level": 1, "parentId": 101 },
{ "_id": 106, "level": 1, "parentId": 101 }
]
},
{
"_id": 102,
"level": 2,
"parentId": 100,
"children": [
{ "_id": 105, "level": 1, "parentId": 102 },
{ "_id": 108, "level": 1, "parentId": 102 }
]
},
{
"_id": 103,
"level": 2,
"parentId": 100,
"children": [
{ "_id": 107, "level": 1, "parentId": 103 },
{ "_id": 109, "level": 1, "parentId": 103 }
]
}
]
}이처럼 parentId 기반의 평면 배열은 해시 맵 하나와 반복문 한 번만으로 손쉽게 트리 구조로 변환할 수 있습니다. 카테고리 메뉴, 댓글 스레드, 조직도처럼 계층형 UI를 구현할 때 널리 활용되는 패턴이니 꼭 익혀두시길 권장합니다.