트리 자료구조와 탐색 알고리즘 정리 (Python 예제 포함)

트리(Tree)란?

트리(Tree) 는 노드(node)와 간선(edge)으로 이루어진 비선형, 계층적 자료구조다.
트리는 부모-자식 관계를 기반으로 하며, 최상단 노드를 루트(root), 자식이 없는 노드를 리프(leaf) 라고 한다.

트리는 다음과 같은 특징을 가진다:

• 각 노드는 하나의 부모만 가진다.
• 같은 부모를 공유하는 노드를 형제(sibling) 라고 한다.
• 데이터를 계층적으로 표현할 때 적합하다.

대표적인 활용 예시:

• 데이터베이스 인덱스
• 파일 시스템 구조
• HTML DOM

---

이진 트리 (Binary Tree)

이진 트리(Binary Tree) 는 각 노드가 최대 두 개의 자식을 가지는 트리다.
왼쪽 자식과 오른쪽 자식으로 나뉘며, 완전 이진 트리(Complete Binary Tree)는 마지막 레벨을 제외한 모든 레벨이 가득 채워진 구조다.

---

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

이진 탐색 트리(BST) 는 다음 규칙을 따른다:

• 왼쪽 서브트리의 값은 부모보다 작다.
• 오른쪽 서브트리의 값은 부모보다 크다.

이 성질 덕분에 탐색, 삽입, 삭제 연산이 평균적으로 O(log n) 시간 복잡도를 가진다.

---

AVL 트리

AVL 트리는 높이 균형을 유지하는 이진 탐색 트리다.
삽입/삭제 시 서브트리의 높이 차이가 1을 초과하면 회전(Rotation) 연산을 수행하여 트리를 재정렬한다.

---

B-트리

B-트리는 데이터베이스, 파일 시스템에서 자주 사용되는 다진 탐색 트리다.
모든 리프 노드는 같은 레벨에 위치하며, 하나의 노드가 여러 개의 키를 가질 수 있다.

---

힙 (Heap)

힙(Heap) 은 우선순위 큐(priority queue) 구현에 사용되는 트리 구조다.

• 최대 힙(Max Heap): 부모 ≥ 자식
• 최소 힙(Min Heap): 부모 ≤ 자식

---

트리 순회(Tree Traversal)

트리 자료구조에서 모든 노드를 방문하는 방법을 순회(Traversal) 라고 한다.
대표적인 방식은 다음과 같다:

1. 중위 순회 (In-order: L → N → R)

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

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

# 예시 트리
root = Node(10)
root.left = Node(5)
root.right = Node(15)

inorder(root)  # 출력: 5 10 15

---

2. 전위 순회 (Pre-order: N → L → R)

def preorder(root):
    if root:
        print(root.key, end=" ")
        preorder(root.left)
        preorder(root.right)

preorder(root)  # 출력: 10 5 15

---

3. 후위 순회 (Post-order: L → R → N)

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.key, end=" ")

postorder(root)  # 출력: 5 15 10

---

4. 너비 우선 탐색 (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(root)  # 출력: 10 5 15

---

5. 깊이 우선 탐색 (DFS)

DFS는 보통 재귀로 쉽게 구현된다.

def dfs(root):
    if root:
        print(root.key, end=" ")
        dfs(root.left)
        dfs(root.right)

dfs(root)  # 출력: 10 5 15

---

마무리

트리 자료구조는 데이터를 계층적으로 표현하고, 탐색 및 정렬을 효율적으로 수행할 수 있는 강력한 도구다.
특히 BST, AVL, B-트리, 힙은 알고리즘 문제뿐 아니라 데이터베이스, 파일 시스템 등 실제 시스템 구현에서도 핵심적인 역할을 한다.

앞으로 트리를 다룰 때는 다양한 순회 방법(In-order, Pre-order, Post-order, BFS, DFS) 과 그 특성을 익혀두는 것이 중요하다.