[자료구조] 트리(Tree)란?

**트리(Tree)**는 계층적(hierarchical) 구조를 가진 데이터 구조로, **노드(Node)**들로 구성됩니다. 트리 구조는 하나의 루트(root) 노드에서 시작해 하위 노드들로 분기하는 방식으로 이루어져 있으며, 각 노드는 여러 개의 자식 노드를 가질 수 있습니다.

1. 기본 구성 요소

• 루트(Root): 트리의 최상위 노드. 트리 구조에서 모든 노드는 루트에서 시작하여 탐색됩니다.
• 노드(Node): 데이터를 포함하는 기본 단위로, 트리의 각 요소를 나타냅니다.
• 간선(Edge): 부모 노드와 자식 노드를 연결하는 선. 트리 내의 노드들은 간선으로 연결됩니다.
• 자식(Child): 부모 노드에서 분기된 하위 노드.
• 부모(Parent): 자식 노드를 가진 노드.
• 리프(Leaf): 자식이 없는 노드, 트리의 끝에 위치하는 노드입니다.
• 깊이(Depth): 특정 노드가 루트로부터 얼마나 떨어져 있는지를 나타내는 값. 루트 노드의 깊이는 0입니다.
• 높이(Height): 트리에서 가장 깊은 리프 노드까지의 거리를 나타내며, 트리의 "높이"를 의미합니다.

2. 트리의 특징

• 계층적 구조: 트리는 부모-자식 관계로 이루어진 계층적인 구조를 가집니다. 이는 트리가 부분적으로 독립된 여러 서브 트리로 나뉠 수 있다는 의미입니다.
• 단방향 연결: 트리의 노드는 단방향으로 연결되어 있으며, 각 노드는 부모 노드만 가리킬 수 있고 자식 노드를 참조할 수 있습니다.
• 순환 없음: 트리 구조는 순환이 없으며, 하나의 루트 노드를 기준으로 모든 노드는 하나의 경로로 연결됩니다.

3. 트리의 종류

• 이진 트리 (Binary Tree):
  • 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다. 이진 트리는 가장 기본적인 트리 형태입니다.
  • 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리의 일종으로, 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 특성을 가집니다.
• 힙(Heap):
  • 완전 이진 트리의 일종으로, 각 부모 노드가 자식 노드보다 우선순위가 높은 성질을 가집니다.
  • 최대 힙 (Max Heap): 부모 노드의 값이 자식 노드보다 크거나 같은 성질을 가집니다.
  • 최소 힙 (Min Heap): 부모 노드의 값이 자식 노드보다 작거나 같은 성질을 가집니다.
• B-트리 (B-Tree):
  • 데이터베이스나 파일 시스템에서 자주 사용되며, 자식 노드가 여러 개일 수 있고, 트리의 균형을 맞추기 위한 구조입니다.
• N-ary 트리 (N-ary Tree):
  • 각 노드가 최대 N개의 자식 노드를 가질 수 있는 트리입니다. N은 2 이상의 자연수일 수 있습니다.
• 트라이(Trie):
  • 문자열을 저장하는 트리 구조로, 각 노드는 문자열의 문자들을 나타내며, 문자열 검색에 최적화되어 있습니다.

4. 트리의 주요 연산

• 삽입(Insertion): 트리에 새로운 노드를 추가하는 작업입니다.
• 삭제(Deletion): 트리에서 특정 노드를 제거하는 작업입니다.
• 탐색(Search): 트리에서 특정 값을 찾는 작업입니다.
• 순회(Traversal): 트리의 모든 노드를 특정 순서로 방문하는 작업입니다. 주요 순회 방식은:
  • 전위 순회 (Pre-order Traversal): 노드 → 왼쪽 자식 → 오른쪽 자식
  • 중위 순회 (In-order Traversal): 왼쪽 자식 → 노드 → 오른쪽 자식
  • 후위 순회 (Post-order Traversal): 왼쪽 자식 → 오른쪽 자식 → 노드
  • 레벨 순회 (Level-order Traversal): 각 레벨별로 노드를 탐색 (너비 우선 탐색, BFS)

5. 트리의 활용 예시

• 파일 시스템: 디렉토리와 파일을 트리 구조로 관리합니다.
• 검색 알고리즘: 이진 탐색 트리나 AVL 트리, B-트리 등이 검색 최적화에 사용됩니다.
• 컴퓨터 네트워크: 라우팅 테이블을 트리 구조로 관리할 수 있습니다.
• 컴파일러: 구문 트리(Syntax Tree)와 같은 트리 구조를 사용하여 프로그램의 문법을 분석합니다.

6. 시각적 예시

• 이진 트리 (Binary Tree):

      1
     / \
    2   3
   / \
  4   5
  

• 이진 탐색 트리 (Binary Search Tree):

      5
     / \
    3   8
   / \  / \
  2  4 6   9
  

트리는 그 구조적 특성으로 인해 효율적인 데이터 검색, 삽입, 삭제 등에서 중요한 역할을 합니다.