[Python] 알고리즘 개념12 - 트리(Tree)와 이진 탐색 트리(BST)

 

 

🚀 1. 트리(Tree)란?

**트리(Tree)**는 계층적인 구조를 가진 비선형 자료구조예요.

 

💡 쉽게 이해하기

• 🌳 **나무(Tree)**처럼 부모 노드(Parent)에서 여러 개의 자식 노드(Child)로 뻗어나가는 구조예요.
• 🏠 가족 관계도, 회사 조직도처럼 계층적인 구조를 표현할 때 유용해요.

 

📌 트리의 기본 개념

• 루트(Root): 트리의 시작 노드
• 노드(Node): 데이터를 저장하는 단위
• 엣지(Edge): 노드 간의 연결선
• 리프(Leaf): 자식이 없는 노드

➡ 트리는 탐색, 정렬, 데이터 구조화 등에 활용돼요.

---

 

 

🚀 2. 이진 트리(Binary Tree)란?

**이진 트리(Binary Tree)**는 각 노드가 최대 두 개의 자식 노드를 가지는 트리예요.

 

📌 이진 트리의 특징

• **왼쪽 자식(Left Child)**과 **오른쪽 자식(Right Child)**만 가질 수 있어요.
• **균형 잡힌 트리(Balanced Tree)**일수록 탐색 속도가 빨라요.

 

💡 이진 트리 구현 (Python 클래스 활용)

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)

➡ 이진 트리는 탐색과 정렬 알고리즘에서 많이 사용돼요!

---

 

 

🚀 3. 이진 탐색 트리(Binary Search Tree, BST)란?

**이진 탐색 트리(BST)**는 이진 트리의 특수한 형태로, 정렬된 데이터를 빠르게 검색할 수 있어요.

 

📌 BST의 특징

• 왼쪽 서브트리: 루트보다 작은 값
• 오른쪽 서브트리: 루트보다 큰 값
• **중위 순회(Inorder Traversal)**하면 항상 오름차순 정렬된 결과를 얻을 수 있어요.

 

💡 이진 탐색 트리 구현

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

    def insert(self, value):
        if value < self.data:
            if self.left is None:
                self.left = BST(value)
            else:
                self.left.insert(value)
        else:
            if self.right is None:
                self.right = BST(value)
            else:
                self.right.insert(value)

# BST 생성 및 삽입
root = BST(10)
root.insert(5)
root.insert(15)
root.insert(2)

➡ BST를 활용하면 검색, 삽입, 삭제 연산을 O(log n) 시간 안에 수행할 수 있어요.

---

 

 

🚀 4. 트리 순회(Tree Traversal)

트리는 선형 자료구조가 아니라서 데이터를 탐색하는 방법이 중요해요.

 

📌 트리 순회 방식

 

✅ 1) 깊이 우선 탐색(DFS, Depth First Search)

• 전위 순회(Preorder): 루트 → 왼쪽 → 오른쪽
• 중위 순회(Inorder): 왼쪽 → 루트 → 오른쪽
• 후위 순회(Postorder): 왼쪽 → 오른쪽 → 루트

 

💡 중위 순회(Inorder) 구현

def inorder_traversal(node):
    if node is not None:
        inorder_traversal(node.left)
        print(node.data, end=' ')
        inorder_traversal(node.right)

inorder_traversal(root)  # 출력: 2 5 10 15

 

 

✅ 2) 너비 우선 탐색(BFS, Breadth First Search)

• 루트부터 시작해 같은 레벨의 노드를 먼저 방문

 

💡 BFS 구현 (큐 활용)

from collections import deque

def bfs(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.data, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

bfs(root)  # 출력: 10 5 15 2

➡ DFS는 재귀적으로 탐색하고, BFS는 큐를 사용해 탐색해요.

---

 

 

🚀 5. 트리와 BST의 시간복잡도 비교

연산 종류 평균 시간복잡도 최악 시간복잡도 (트리가 편향된 경우)

삽입(Insert)	O(log n)	O(n)
삭제(Delete)	O(log n)	O(n)
검색(Search)	O(log n)	O(n)

➡ BST가 균형 잡힌 상태라면 O(log n)의 속도로 탐색이 가능해요!

---

 

 

🚀 6. 트리와 BST의 활용 예시

 

📌 트리와 BST는 어디에서 사용될까요?

1. 데이터베이스 인덱스 (B-Tree) → 빠른 검색을 위해 사용
2. 파일 시스템 (디렉터리 구조) → 트리 형태로 파일을 관리
3. 검색 엔진의 자동완성 기능 (Trie) → 문자열 탐색에 활용
4. AI 및 게임 개발 (의사 결정 트리, Minimax 알고리즘) → AI의 의사결정 모델
5. 이진 탐색 (Binary Search) 최적화 → 큰 데이터에서 빠르게 검색

➡ 트리는 다양한 분야에서 중요한 역할을 합니다! 😊

---

 

 

✅ 마무리 정리

• 트리는 계층적인 구조를 가진 자료구조이며, 탐색과 정렬에 유용합니다.
• 이진 탐색 트리(BST)는 왼쪽은 작은 값, 오른쪽은 큰 값으로 정렬됩니다.
• DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 활용하여 데이터를 탐색할 수 있습니다.
• BST는 탐색, 삽입, 삭제 연산을 O(log n)의 속도로 수행할 수 있습니다.