트리(Tree) 자료구조 쉽게 이해하기: 이진트리부터 탐색까지 한 번에 정리

트리(Tree) 자료구조 쉽게 이해하기: 이진트리부터 탐색까지 한 번에 정리

자료구조를 조금 더 깊이 공부하면 반드시 만나게 되는 것이 바로 **트리(Tree)**입니다. 트리는 계층적 구조를 표현할 수 있는 비선형 자료구조로, 디렉토리 구조, 조직도, 게임 AI, 컴파일러 등 수많은 실무 영역에서 쓰입니다.

이번 글에서는 트리의 기본 개념부터 이진트리, 이진탐색트리(BST), 순회(Traversal) 방식까지 정리하고, 실제 코드로 어떻게 구현되는지도 자세히 알아보겠습니다.

---

🌳 트리(Tree)란?

트리는 **계층 구조(Hierarchical Structure)**를 표현하기 위한 비선형 자료구조입니다.
노드(Node)들과 노드 간의 관계(간선, Edge)로 구성되며, 루트(Root)부터 리프(Leaf)까지 이어집니다.

✅ 기본 용어 정리

용어 설명

루트 노드(Root)	트리의 시작점 (최상단 노드)
부모 노드(Parent)	다른 노드를 가리키는 노드
자식 노드(Child)	부모로부터 연결된 하위 노드
리프 노드(Leaf)	자식이 없는 노드
서브트리(Subtree)	특정 노드를 루트로 하는 하위 트리
깊이(Depth)	루트에서 특정 노드까지의 거리
높이(Height)	리프까지의 최대 거리

---

✅ 이진트리(Binary Tree)

이진트리는 모든 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.

🔹 이진트리 구조

      1
     / \
    2   3
   / \   \
  4   5   6

📌 파이썬 구현 예시

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

# 이진트리 구성
root = Node(1)
root.left = Node(2)
root.right = Node(3)

root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)

---

🔍 트리 순회(Traversal) 방식

반응형

트리는 선형 구조가 아니기 때문에 **노드를 방문하는 방식(순회)**이 중요합니다.
가장 대표적인 세 가지 순회 방식은 다음과 같습니다:

1. 중위 순회 (In-order): 왼쪽 → 루트 → 오른쪽

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data, end=' ')
        inorder(node.right)

inorder(root)  # 출력: 4 2 5 1 3 6

2. 전위 순회 (Pre-order): 루트 → 왼쪽 → 오른쪽

def preorder(node):
    if node:
        print(node.data, end=' ')
        preorder(node.left)
        preorder(node.right)

preorder(root)  # 출력: 1 2 4 5 3 6

3. 후위 순회 (Post-order): 왼쪽 → 오른쪽 → 루트

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data, end=' ')

postorder(root)  # 출력: 4 5 2 6 3 1

---

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

BST는 왼쪽 자식 < 루트 < 오른쪽 자식 규칙을 따르는 이진트리입니다.
탐색, 삽입, 삭제 연산이 평균적으로 **O(log n)**의 성능을 갖습니다.

📌 삽입 함수 구현 예시

def insert(node, data):
    if node is None:
        return Node(data)
    if data < node.data:
        node.left = insert(node.left, data)
    else:
        node.right = insert(node.right, data)
    return node

# BST 생성
bst_root = Node(10)
insert(bst_root, 5)
insert(bst_root, 15)
insert(bst_root, 3)
insert(bst_root, 7)

📌 탐색 함수 구현

def search(node, target):
    if node is None:
        return False
    if node.data == target:
        return True
    elif target < node.data:
        return search(node.left, target)
    else:
        return search(node.right, target)

print(search(bst_root, 7))   # True
print(search(bst_root, 20))  # False

---

📊 트리 vs 배열/리스트 성능 비교

연산 배열/리스트 이진 탐색 트리

검색	O(n)	O(log n)
삽입	O(1) or O(n)	O(log n)
삭제	O(n)	O(log n)
정렬	필요	자동 정렬 유지

---

🌐 트리 자료구조가 사용되는 곳

• 디렉토리 구조, 파일 시스템
• DOM 구조 (웹 개발)
• 게임 AI (Minimax 트리)
• 파싱 트리 (컴파일러)
• 힙 정렬(Heap Sort), 우선순위 큐(Priority Queue)

---

📌 결론 및 요약

• 트리는 계층적 구조를 표현하는 자료구조로, 다양한 분야에서 필수적으로 사용됩니다.
• 이진트리는 가장 기본적인 트리 형태이며, 순회 방식에 따라 다양한 알고리즘 문제에 활용됩니다.
• 이진 탐색 트리는 빠른 탐색과 삽입/삭제가 가능한 효율적인 트리입니다.
• 실전에서는 BST 외에도 AVL 트리, 힙, B-트리 등 다양한 변형이 존재합니다.

👉 다음 글에서는 이진 탐색(Binary Search)와 정렬 알고리즘을 결합한 실전 예제를 다루겠습니다!

---

📚 참고자료 및 출처

• 『Introduction to Algorithms (CLRS)』
• GeeksforGeeks – Tree Data Structure
• 『파이썬으로 배우는 자료구조』

---