[자료구조&알고리즘] 트리(Tree)

❓트리(Tree)란?

트리는 계층적인 구조를 표현하는 데 사용되는 대표적인 자료구조로, 여러 노드(node)와 이들을 연결하는 간선(edge)로 이루어진 비선형 자료구조. 실제 나무를 거꾸로 놓은 것과 같은 형태를 가지며, 컴퓨터의 디렉토리 구조, 조직도, 데이터베이스 인덱스 등 다양한 분야에서 활용

---

🧩트리의 구조와 기본 용어

        A
      / | \
     B  C  D
    /|\   / \
   E F G H   I

• 노드(Node): 트리의 기본 단위로, 데이터(값)와 하위 노드에 대한 포인터를 가짐. (위 그림의 A~I)
• 간선(Edge): 노드와 노드를 연결하는 선.
• 루트 노드(Root Node): 트리의 최상위에 위치하며, 부모가 없는 노드. A가 루트 노드
• 부모 노드(Parent Node): 자식 노드를 가진 노드.
• 자식 노드(Child Node): 부모 노드의 하위에 있는 노드. B는 E, F, G의 부모, E, F, G는 B의 자식
• 형제 노드(Sibling Node): 같은 부모를 가진 노드들.  E, F, G는 서로 형제 노드
• 리프 노드(Leaf Node, 단말 노드): 자식이 없는 노드. E, F, G, H, I는 리프 노드
• 내부 노드(Internal Node): 자식 노드를 가진 노드. B는 내부 노드
• 깊이(Depth): 루트에서 해당 노드까지의 간선 수.
• 레벨(Level): 트리의 층수(루트는 0 또는 1). E의 깊이/레벨은 2
• 높이(Height): 해당 노드에서 리프 노드까지의 가장 긴 경로의 간선 수. 위 트리의 높이는 2(간선 기준)
• 차수(Degree): 한 노드가 가진 자식 노드의 수. B의 차수는 3(E, F, G)
• 경로(Path): 한 노드에서 다른 노드로 가는 노드들의 순서.
• 서브트리(Subtree): 특정 노드를 루트로 하는 하위 트리. B와 그 자식들 전체가 하나의 서브트리

---

💠트리의 특징

• 비선형 자료구조: 배열, 리스트와 달리 데이터가 순차적으로 저장되지 않음.
• 계층적 구조: 부모-자식 관계로 구성되어 계층적인 데이터 표현에 적합.
• 사이클 없음: 임의의 노드에서 시작해 자기 자신으로 돌아오는 경로(사이클)가 존재하지 않음.
• 단일 루트: 반드시 하나의 루트 노드만 존재.
• 간선의 수: 노드가 N개이면 항상 N-1개의 간선을 가짐.
• 모든 노드는 하나의 부모만 가질 수 있음(루트 제외).

---

🌲트리의 종류

1. 일반 트리

• 자식 노드 수에 제한이 없음

2. 이진 트리(Binary Tree)

• 각 노드가 최대 2개의 자식(왼쪽, 오른쪽)만 가짐

 

      A
     / \
    B   C
   / \   \
  D   E   F

• 각 노드의 자식은 최대 2개.

3. 완전 이진 트리(Complete Binary Tree)

• 마지막 레벨을 제외한 모든 레벨이 노드로 가득 차 있고, 마지막 레벨은 왼쪽부터 채워짐

 

      A
     / \
    B   C
   / \  /
  D  E F

• D, E, F는 마지막 레벨.

4. 포화 이진 트리(Perfect Binary Tree)

• 모든 리프 노드가 동일한 깊이에 있고, 모든 내부 노드가 두 자식 노드를 가짐

 

      A
     / \
    B   C
   / \ / \
  D  E F  G

• 모든 레벨이 가득 참.

5. 편향 트리(Skew Tree)

• 모든 노드가 한쪽 자식만 가짐

 

A
 \
  B
   \
    C
     \
      D

• 오른쪽 편향 트리.

6. 트라이(Trie)

• 문자열 검색에 특화된 트리

 

root
 ├─ a ─ l ─ g ─ o
 ├─ h ─ i ─ g ─ h
 └─ r ─ e ─ b ─ r ─ o
           └─ p ─ l ─ a ─ y

• 각 경로가 하나의 문자열을 나타냄8.

7. m-원 탐색 트리(m-way Search Tree): 한 노드가 최대 m개의 자식을 가질 수 있는 트리.

---

💿트리의 활용 예시

• 파일 시스템: 디렉토리와 파일 구조 표현.
  /
  ├── home
  │   ├── user1
  │   └── user2
  └── etc
      ├── config
      └── hosts
  
  
• 데이터베이스 인덱스: B-트리, B+트리 등.
• 계층적 데이터 표현: 조직도, 가계도 등.
• 효율적인 탐색, 삽입, 삭제: 이진 탐색 트리, 힙(Heap) 등에서 사용.

---

🔹트리와 그래프의 관계

트리는 그래프의 하위 개념으로, 방향성이 있고 사이클이 없는 연결 그래프의 일종입니다. 모든 노드는 루트에서 시작해 단 하나의 경로로만 접근할 수 있습니다.