소개

트리 데이터 구조가 있다고 가정해 보겠습니다. 조직 계층 구조, 프로젝트 분류, 동물/식물 분류 등이 될 수 있습니다. 다음은 트리 구조의 예입니다.



애플리케이션에서 특히 일대다 상위/하위 노드 관계가 있는 경우 이 정보를 다음 형식으로 저장하는 것이 상당히 일반적입니다.

const data = [
  { id: 56, parentId: 62 },
  { id: 81, parentId: 80 },
  { id: 74, parentId: null },
  { id: 76, parentId: 80 },
  { id: 63, parentId: 62 },
  { id: 80, parentId: 86 },
  { id: 87, parentId: 86 },
  { id: 62, parentId: 74 },
  { id: 86, parentId: 74 },
];

그렇다면 이 객체 배열 형식에서 계층적 트리 형식으로 어떻게 전환할까요? JavaScript 개체 참조를 활용하면 실제로 이것은 상당히 쉬운 작업이 됩니다. 재귀없이 O(n) 시간에 수행할 수 있습니다.

몇 가지 빠른 용어

우리가 같은 언어로 말하고 있는지 확인하기 위해 제가 사용할 수 있는 몇 가지 용어를 빠르게 살펴보겠습니다. 배열의 각 요소(즉, 트리의 각 원)는 "노드"입니다. 노드는 여러 노드의 "부모"가 될 수 있고 한 노드의 "자식"이 될 수 있습니다. 위 그림에서 노드 86은 노드 80과 노드 87의 "부모"입니다. 노드 86은 노드 74의 "자식"입니다. 트리의 최상위 노드는 "루트"입니다.

전반적인 방법론

트리를 구축하려면 다음을 수행해야 합니다.

데이터 배열을 반복합니다

.

현재 요소의 상위 요소 찾기

부모 요소의 개체에서 자식에 대한 참조를 추가합니다

.

요소에 대한 부모가 없으면 트리의 "루트"요소가 될 것임을 알 수 있습니다

.

우리는 객체 트리 아래에서 참조가 유지될 것이라는 사실을 깨달아야 합니다. 이것이 우리가 O(n) 시간에 이를 달성할 수 있는 이유입니다!

ID-to-Array 위치 맵 만들기

완전히 필요한 것은 아니지만 요소 ID를 배열 인덱스에 매핑하는 것으로 시작하겠습니다. 이렇게 하면 때가 되면 요소의 부모에 대한 참조를 추가하는 데 도움이 됩니다.

const idMapping = data.reduce((acc, el, i) => {
  acc[el.id] = i;
  return acc;
}, {});

이 매핑은 다음과 같이 나옵니다. 이것이 유용한 이유를 곧 알게 될 것입니다.

{
  56: 0,
  62: 7,
  63: 4,
  74: 2,
  76: 3,
  80: 5,
  81: 1,
  86: 8,
  87: 6,
};

트리 만들기

트리를 만들 준비가 되었습니다! 개체를 반복하고 각 항목의 부모에 대한 참조를 할당해 봅시다. 부모를 찾는 데 도움이 되도록 idMapping를 사용하는 위치에 유의하십시오.

let root;
data.forEach(el => {
  // Handle the root element
  if (el.parentId === null) {
    root = el;
    return;
  }
  // Use our mapping to locate the parent element in our data array
  const parentEl = data[idMapping[el.parentId]];
  // Add our current el to its parent's `children` array
  parentEl.children = [...(parentEl.children || []), el];
});

그리고 그게 다야! 다음을 확인하기 위해 트리 루트를 확인할 수 있습니다console.log.

console.log(root);

{
  id: 74,
  parentId: null,
  children: [
    {
      id: 62,
      parentId: 74,
      children: [{ id: 56, parentId: 62 }, { id: 63, parentId: 62 }],
    },
    {
      id: 86,
      parentId: 74,
      children: [
        {
          id: 80,
          parentId: 86,
          children: [{ id: 81, parentId: 80 }, { id: 76, parentId: 80 }],
        },
        { id: 87, parentId: 86 },
      ],
    },
  ],
};

이것이 작동하는 이유

이것이 작동하는 이유를 이해하는 가장 좋은 방법은 데이터 배열의 각 요소가 메모리에 있는 개체에 대한 참조이고, el 루프의 forEach 변수가 메모리에 있는 개체(메모리에 있는 해당 개체를 참조함)를 기억하는 것입니다. 데이터 배열 요소가 참조하고 있음) 및 parentEl는 메모리의 객체(데이터 배열에서 참조되는 객체 중 하나)도 참조합니다.

메모리의 개체에 자식 참조 배열이 있는 경우 해당 자식은 점점 커지는 자식 참조 배열을 가질 수 있습니다. 이것은 모두 참조에 의해 수행되므로 자식 중 하나를 수정할 때 부모에게 아무 것도 말할 필요가 없습니다.

결론

개체 참조는 항상 더 많은 연구와 이해를 사용할 수 있다고 믿는 JavaScript의 기본 개념 중 하나입니다. 실제로 이 개념을 이해하면 까다로운 버그를 피하는 데 도움이 되고 겉보기에 복잡해 보이는 문제에 대한 비교적 간단한 솔루션을 제공할 수 있습니다.