자 바스 크 립 트 구조 트 리 구조의 효율 적 인 알고리즘

머리말
우 리 는 조직 등급,성 시 현 또는 동 식물 분류 등 나무 데이터 구 조 를 자주 만난다.다음은 트 리 구조의 예 입 니 다.

실제 응용 에서 흔히 볼 수 있 는 방법 은 이런 정 보 를 아래 의 구조 로 저장 하 는 것 이다.특히 1 쌍 이 넘 는 부모/자식 노드 관계 가 존재 할 때:

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 },
];

그렇다면 어떻게 이런 대상 배열 형식 을 등급 트 리 형식 으로 바 꿉 니까?사실 자 바스 크 립 트 대상 이 인용 하 는 특성 을 이용 하여 실현 하 는 것 은 매우 간단 할 것 이다.그것 은 귀환 하지 않 고 O(n)시간 내 에 완성 할 수 있다.
술어
서술 의 편 의 를 위해 서 우 리 는 먼저 몇 개의 용 어 를 정의 한다.우 리 는 배열 의 모든 요 소 를'노드'라 고 부른다.노드 는 여러 노드 의'부모 노드'일 수도 있 고 특정한 노드 의'하위 노드'일 수도 있다.위의 그림 에서 노드 86 은 노드 80 과 노드 87 의'부모 노드'이 고 노드 86 은 노드 74 의 서브 노드 이다.나무의 맨 윗부분 노드 를'뿌리 노드'라 고 부른다.
사고의 방향
나무 구 조 를 만 들 기 위해 서 는 다음 과 같은 것 이 필요 하 다.
데이터 배열
현재 원소 의 부모 원 소 를 찾 습 니 다

부모 요소 대상 에 이 하위 요소 에 대한 인용 을 추가 합 니 다

4.567917.요소 가 부모 요소 가 없다 면 우 리 는 그것 이 나무의 뿌리 노드 라 고 생각한다.
대상 트 리 에 저 장 된 인용 을 볼 수 있 습 니 다.이것 이 바로 우리 가 O(n)시간 안에 이 임 무 를 완성 할 수 있 는 이유 입 니 다!
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 => {
  //      
  if (el.parentId === null) {
    root = el;
    return;
  }
  //          
  const parentEl = data[idMapping[el.parentId]];
  //             `children`   
  parentEl.children = [...(parentEl.children || []), el];
});

일 을 끝내다console.log 로 root 인쇄 하기:

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 },
      ],
    },
  ],
};
의 원리
왜 이렇게 할 수 있 지?이것 은 data 배열 의 모든 요 소 는 메모리 에 있 는 대상 참조 입 니 다.foreach 순환 에 있 는 el 변 수 는 메모리 에 있 는 대상 을 가리 키 고 parentEl 도 대상 을 참조 하기 때 문 입 니 다.
메모리 의 한 대상 이 children 배열 을 참조 하면 이 하위 요 소 는 자신의 하위 요소 배열 을 참조 할 수 있 습 니 다.이러한 관련 관 계 는 모두 인용 을 통 해 이 루어 집 니 다.
총결산
대상 인용 은 자 바스 크 립 트 에서 가장 기본 적 인 개념 중 하나 로 더 많은 학습 과 이해 가 필요 하 다.이 개념 을 진정 으로 이해 하면 까다 로 운 bug 를 피 할 수 있 을 뿐만 아니 라 복잡 해 보 이 는 문제 에 상대 적 으로 간단 한 해결 방안 을 제공 할 수 있다.
이상 은 자바 스 크 립 트 구조 트 리 구조의 효율 적 인 알고리즘 에 대한 상세 한 내용 입 니 다.자바 스 크 립 트 구조 트 리 구조 에 관 한 알고리즘 에 관 한 자 료 는 다른 관련 글 에 주목 하 시기 바 랍 니 다!