[알고리즘 자료구조] JavaScript in Tree

1. Tree

1-1. Tree란

• 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리구조 라고 부른다.
• 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조로, 아래로만 뻗어 나가기 때문에 싸이클이 없다.
• 즉, 싸이클이 없는 하나의 연결 그래프라고 할 수 있다.

1-2. 용어 설명

• 노드(Node): 트리 구조를 이루는 모든 개별 데이터
• 루트(Root): 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node): 두 노드가 상하관계로 연결되어 있을 때, 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node): 두 노드가 상하관계로 연결되어 있을 때, 상대적으로 루트에서 멀리있는 노드
• 리프(Leaf): 트리 구조의 끝 지점이며 자식 노드가 없는 노드
• 깊이(depth): 루트에서 하위 계층의 특정 노드까지의 깊이
  ex) root = 0 / Q, R = 1 / A, B, C, D = 2
• 레벨(level): 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있으며, 같은 레벨에 나란히 있는 노드를 형제노드(Sibling node) 라고 한다.
• 높이(height): 리프노드(최하단)를 기준으로 루트까지의 높이를 표현할 수 있다.
• 서브 트리: 큰 트리 내부의 트리구조를 갖춘 작은 트리를 의미한다.

1-3. 사용 예시

컴퓨터의 디렉터리 구조

어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더 또는 다운로들 폴더 등에서 다른 폴더에 진입하고, 그 안에서 또 다른 폴더에 진입하는 식으로 찾는데, 모든 폴더는 /에서 시작되어 가지를 뻗어나가는 형태이다.