[자료구조] Tree 트리

⚡️ Tree

[그림] 트리 구조 예시

• 자료구조 Tree는 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아서 트리 구조라고 부른다.
• 자료구조 Tree는 그래프의 여러 구조 중 무방향 그래프의 한 구조이다.
• 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다.
• 트리 구조는 데이터를 순차적으로 나열시킨 선형 구조가 아니라,
  하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.
• 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.
• 트리 구조는 루트라는 하나의 꼭짓점 데이터를 시작으로, 여러 개의 데이터를 간선으로 연결한다.
• 트리 구조는 각 데이터를 노드라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가진다.
• 트리 구조에서 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드라고 부른다.
• 자료구조 Tree는 깊이와 높이, 레벨 등을 측정할 수 있다.

❗️용어 정리

[그림] 자료구조 트리 용어 정리

👉 노드(Node)

• 노드란 트리 구조를 이루는 모든 개별 데이터

👉 루트(Root)

• 루트란 트리 구조의 시작점이 되는 노드

👉 부모 노드(Parent node)

• 부모 노드란 두 노드가 상하관계로 연결되어 있을 때, 상대적으로 루트에서 가까운 노드

👉 자식 노드(Child node)

• 자식 노드란 두 노드가 상하관계로 연결되어 있을 때, 상대적으로 루트에서 먼 노드

👉 리프(Leaf)

• 리프란 트리 구조의 끝지점이고, 자식 노드가 없는 노드

👉 깊이 (depth)

• 트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다.
• 루트 노드는 지면에 있는 것처럼 깊이가 0이다.
• 그림에서 루트 A의 depth는 0이고, B와 C의 깊이는 1이다.
• 그림에서 D, E, F, G의 깊이는 2이다.

👉 레벨(Level)

• 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있다.
• depth가 0인 루트 A의 level은 1이다.
• depth가 1인 B와 C의 level은 2이다.
• 그림에서 D, E, F, G의 레벨은 3이다.
• 같은 레벨에 나란히 있는 노드를 형제 노드(sibling Node) 라고 한다.

👉 높이(Height)

• 트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다.
• 트리 구조에서 리프 노드와 직간접적으로 연결된 노드의 높이를 표현한다.
• 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다.
• 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다.
• 그림에서 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)도 서브 트리이다.

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

자료구조는 사람이 사용하기에 편리하려고, 사용하기 좋으려고 만들어진 것이다.

 

---

 

❗️트리의 실사용 예제

👉 컴퓨터의 디렉토리 구조

• 어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고,
  또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾는다.
• 모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작되어, 가지를 뻗어나가는 모양새를 띈다.
• 하나의 폴더 안에 여러 개의 폴더가 있고, 또 그 여러 개의 폴더 안에 또 다른 폴더나 파일이 있다.
• 제일 첫 번째 폴더에서 출발하여 도착하려는 폴더로 가는 경로는 유일하다.
• 사용자들이 사용하기 편하게 사용하기 위한 파일 시스템 등에서는 트리 구조를 이용해 만들어져 있다.

👉 트리의 다른 예시

• 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등.

출처: https://hanamon.kr/%ec%9e%90%eb%a3%8c%ea%b5%ac%ec%a1%b0-tree-%ed%8a%b8%eb%a6%ac/