🖍️ 트리란?

일련의 연결된 노드로 트리 구조를 시뮬레이션하는 계층적 데이터 구조

• 특징

  • 계층적 구조

    트리에는 루트라는 최상위 노드가 있으며, 
    이 노드에는 0개 이상의 자식 노드가 있으며 
    각 노드는 자체 자식을 가질 수 있음
    
    이렇게 하면 계층 구조(상위-하위 관계)가 생성

  • 노드

    트리의 각 요소는 노드라 함
    최상위 노드는 루트 노드, 트리는 오직 하나의 루트만 가질 수 있음
    자식이 없는 노드를 리프 노드 or 외부 노드라 함
    하나 이상 자식이 있으면 노드를 내부 노드라 함

  • Edges/Links

    노드는 Edge 로 연결, 트리의 Edge 는 부모-자식 관계
    루트에서 노드까지의 간선 수는 노드의 깊이

  • 하위트리

    하위 트리는 모든 하위 항목을 포함하는 트리의 모든 노드
    각 하위 노드는 하위 트리의 루트로 볼 수 있음

  • 비순환

    트리는 비순환적
    순환이나 닫힌 루프가 없음

  • 경로

    경로는 노드와 자손을 연결하는 일련의 노드의 간선

  • 높이 및 깊이

    노드의 높이는 해당 노드와 리프 사이의 가장 긴 하향 경로에 있는 가장 자리 수
    트리의 높이는 뿌리의 높이
    
    노드의 깊이는 노드에서 트리의 루트 노드까지의 간선 수

• 종류

  • 이진 트리
  • 이진 검색 트리
  • 균형 트리

class TreeNode {
    constructor(value) {
        this.value = value;
        this.children = [];
    }

    addChild(node) {
        this.children.push(node);
    }
}

// Example of creating a tree
let root = new TreeNode(1);
let child1 = new TreeNode(2);
let child2 = new TreeNode(3);

root.addChild(child1);
root.addChild(child2);

child1.addChild(new TreeNode(4));
child1.addChild(new TreeNode(5));

child2.addChild(new TreeNode(6));

• 대표적인 알고리즘

  • BFS (너비 우선 탐색)
    • 다음 레벨로 이동 전 현재 깊이 모든 노드 방문
  • DFS (깊이 우선 탐색)
    • 스택을 사용한 반복적 접근 방식

디버깅을 위해 트리에 1억 개의 데이터 조각을 모두 기록하는 방법


순회에는 깊이 우선 검색(DFS) 또는 너비 우선 검색(BFS)을 사용
이러한 방법을 사용하면 각 노드를 한 번만 방문


JavaScript에서 재귀 DFS는 노드 수가 너무 많아 스택 오버플로가 발생 가능
스택(DFS의 경우) 또는 대기열(BFS의 경우)을 사용하는 반복적 접근 방식이 더 적절