트리 (Tree) 자료구조

📌 개요

트리(Tree)는 계층적 구조를 표현하는 비선형 자료구조입니다.
각 요소(노드, Node)는 부모와 자식 간의 관계를 가지며, 루트(Root)에서 시작하여 가지를 뻗어나가는 형태를 가집니다.

✅ 트리의 특징:

• 순환(Cycle)이 없는 그래프
• 계층적 구조 (부모-자식 관계)
• DFS, BFS 등 다양한 탐색 방법 존재
• 이진 탐색 트리(BST), 힙(Heap), AVL 트리 등 다양한 응용 가능

---

📌 트리의 기본 개념

1. 트리의 기본 용어

용어	설명
노드(Node)	트리의 각 요소
루트 노드(Root Node)	트리의 최상위 노드
부모 노드(Parent Node)	특정 노드의 상위 노드
자식 노드(Child Node)	특정 노드의 하위 노드
형제 노드(Sibling Node)	같은 부모를 가진 노드들
잎 노드(Leaf Node)	자식이 없는 노드
깊이(Depth)	루트에서 특정 노드까지의 거리
높이(Height)	특정 노드에서 가장 깊은 노드까지의 거리

---

📌 트리의 종류

1. 일반 트리 (General Tree)

• 노드가 여러 개의 자식을 가질 수 있는 트리
• 파일 시스템, 계층적 데이터 구조에서 사용

2. 이진 트리 (Binary Tree)

• 각 노드가 최대 2개의 자식(왼쪽, 오른쪽)을 가질 수 있는 트리
• 빠른 탐색 및 정렬을 위해 활용됨

📌 이진 트리의 종류

1. 이진 탐색 트리 (Binary Search Tree, BST)

   • 왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 가짐
   • 빠른 탐색, 삽입, 삭제 가능 (O(log N))

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

   • 왼쪽부터 채워지는 이진 트리
   • 힙(Heap) 구조에서 사용됨

3. 균형 이진 트리 (Balanced Binary Tree)

   • 모든 서브트리의 높이 차이가 1 이하
   • AVL 트리, 레드-블랙 트리 등이 있음

4. 힙(Heap)

   • 완전 이진 트리 구조
   • 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 구분
   • 우선순위 큐(Priority Queue)에 사용됨

---

📌 이진 트리의 구현 (Python)

1. 노드(Node) 클래스 정의

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

✅ 각 노드는 key 값을 가지며, 왼쪽(left), 오른쪽(right) 자식 노드를 가질 수 있음

---

2. 이진 탐색 트리 (BST)

📌 삽입 (Insertion)

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        self.root = self._insert_recursive(self.root, key)

    def _insert_recursive(self, node, key):
        if node is None:
            return Node(key)
        if key < node.key:
            node.left = self._insert_recursive(node.left, key)
        else:
            node.right = self._insert_recursive(node.right, key)
        return node

✅ 작은 값은 왼쪽, 큰 값은 오른쪽에 배치하여 정렬됨

---

📌 탐색 (Search)

def search(node, key):
    if node is None or node.key == key:
        return node
    if key < node.key:
        return search(node.left, key)
    return search(node.right, key)

✅ 이진 탐색을 활용하여 O(log N)의 시간 복잡도로 탐색 가능

---

📌 삭제 (Deletion)

def delete(node, key):
    if node is None:
        return node
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        temp = find_min(node.right)
        node.key = temp.key
        node.right = delete(node.right, temp.key)
    return node

def find_min(node):
    while node.left:
        node = node.left
    return node

✅ 삭제 과정에서 후계 노드를 찾아 대체하는 방식 사용

---

📌 트리의 순회 (Tree Traversal)

트리에서 모든 노드를 방문하는 방법은 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색) 이 있습니다.

1. 깊이 우선 탐색 (DFS)

• 전위 순회 (Preorder) → Root → Left → Right
• 중위 순회 (Inorder) → Left → Root → Right
  → 이진 탐색 트리에서 중위 순회를 하면 정렬된 결과가 나옴
• 후위 순회 (Postorder) → Left → Right → Root

📌 중위 순회 (Inorder Traversal) 구현

def inorder(node):
    if node:
        inorder(node.left)
        print(node.key, end=" ")
        inorder(node.right)

✅ 이진 탐색 트리에서 중위 순회를 하면 오름차순 정렬된 값이 출력됨

---

2. 너비 우선 탐색 (BFS)

BFS는 큐(Queue)를 이용하여 레벨별로 순회합니다.

📌 BFS 구현

from collections import deque

def bfs(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.key, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

✅ BFS는 최단 경로 문제 해결에도 유용함

---

📌 트리의 응용

✅ 1. 이진 탐색 트리 (BST)

• 데이터 삽입, 삭제, 탐색을 O(log N) 시간 복잡도로 수행 가능
• 데이터베이스 인덱스, 검색 시스템 등에 사용

✅ 2. 힙 (Heap)

• 최대값/최소값을 빠르게 찾기 위한 자료구조
• 우선순위 큐, 작업 스케줄링 등에 활용

✅ 3. 트라이 (Trie)

• 문자열 탐색을 빠르게 수행하기 위한 트리 구조
• 자동 완성, 검색 엔진 등에 사용

✅ 4. AVL 트리, 레드-블랙 트리

• 균형을 유지하는 트리로 O(log N)의 성능을 보장
• 데이터베이스, 네트워크 라우팅에서 사용

---

📌 결론

• 트리는 계층적인 데이터 구조로, 다양한 응용이 가능
• 이진 탐색 트리는 탐색 및 정렬에 유리한 구조
• 트리 순회 방법 (DFS, BFS)을 잘 이해하고 활용해야 함
• 균형 트리(AVL, 레드-블랙 트리) 등을 통해 시간 복잡도를 최적화 가능

🚀 트리 자료구조는 알고리즘 문제 풀이에서 매우 자주 등장하는 핵심 개념이므로, 반드시 익혀야 합니다!