[자료구조] Tree

1. 트리(Tree)란

• 나무를 거꾸로 뒤집어 놓은 듯한 구조
• 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조
• 단방향 그래프의 한 구조
• 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
• 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조

---

2.Tree의 특징

• 루트 (root)
  • 트리 구조의 시작점이 되는 노드
• 노드 (node)
  • 트리 구조를 이루는 모든 개별 데이터
  • 부모 노드, 자식 노드, 리프 노드(자식이 없는 노드)
• 깊이 (depth)
  • 루트 노드로 부터 하위 특정 노드까지의 깊이 표현 가능
  • 루트 노드는 지면에 있는 것 같이 깊이가 0
• 높이 (height)
  • 리프 노드를 기준으로 표현 가능
  • 부모노드는 자식 노드의 높이 중 가장 높은 높이에 +1 값
• 레벨 (level)
  • 같은 깊이를 가진 노드들을 묶어서 표현 가능
• 서브 트리 (sub tree)
  • 트리 내부에 트리 구조를 갖춘 작은 트리
  • 즉, 그림 속 (D, H, I)로 이루어진 작은 트리 뿐 아니라 (B, D, E)나 (C, F, G, J)도 서브 트리

 

---

3.Tree의 실사용 예제

• 예 : 컴퓨터의 디렉토리 구조

          ➡️ 컴퓨터에서 파일을 찾을 때, 폴더에 진입하여 그 하위 폴더에 진입하여 찾음.

                >> 가지가 뻗어나가는 모양 같음.

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