Tree

그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태

• 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료구조
• 데이터를 순차적으로 나열시킨 선형구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조
• 계층적으로 표현되고 아래로만 뻗어나가기 때문에 사이클(cycle)이 없으며 하나의 연결 그래프다.
  • 사이클 : 시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아가는 것.

🌲 Tree의 구조와 특징

• 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다.
• 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.
• 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다.

깊이 (depth)

루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현.
0부터 시작한다.

루트 A의 depth : 0
B와 C depth : 1
D, E, F, G depth : 2

레벨(Level)

같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현.
1부터 시작한다.
형제 노드(Sibling Node) : 같은 레벨에 나란히 있는 노드

depth가 0인 루트 A의 level : 1
depth가 1인 B와 C의 level : 2
D, E, F, G의 레벨 : 3

높이(Height)

리프 노드를 기준으로 루트까지의 높이(height)를 표현
리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다.

H, I, E, F, J의 높이 : 0
D와 G의 높이 : 1
B와 C의 높이 : 2
이때 B는 D의 height + 1 을, C는 G의 height + 1 을 높이로 가진다. 따라서, 루트 A의 높이는 3이다.

서브 트리(Sub tree)

트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리.
(D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E)나 (C, F, G, J)도 서브 트리다.

자료구조는 자료의 집합을 구조화하고, 이를 표현하는 데에 초점이 맞춰져 있다.

용어정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

---

🌲 Tree의 실사용 예제

• 가장 대표적인 예 : 컴퓨터의 디렉토리 구조.
  • 모든 폴더는 하나의 폴더(루트 폴더,/)에서 시작되어, 가지를 뻗어나가는 모양새
  • 하나의 폴더 안에 여러개의 폴더가 있고 그 안에 또 다른 폴더나 파일이 있다.
• 다른 예 : 월드컵 토너먼트 대진표, 가계도, 조직도 등