트리(Tree): 계층적 데이터 구조의 개념과 활용

🔹 트리란?

1. 트리(Tree)의 정의

트리(Tree)는 계층적(Hierarchical) 구조를 가지며, 부모-자식 관계로 데이터를 조직하는 비선형 데이터 구조입니다. 트리는 파일 시스템, 데이터베이스 인덱싱, 인공지능, 네트워크 라우팅 등의 다양한 분야에서 활용됩니다.

✅ 트리의 주요 특징:

• 노드(Node)와 간선(Edge)으로 구성
• 루트(Root) 노드에서 시작하여 하위 노드(Child Nodes)로 확장
• 순환이 없는 비선형 구조(Acyclic Structure)
• 탐색, 정렬, 계층적 데이터 관리에 유용

📌 트리는 계층적 데이터 구조를 표현할 때 가장 효과적인 방법 중 하나입니다.

---

🔹 트리의 기본 용어

✅ 루트 노드(Root Node): 트리의 최상위 노드
✅ 부모 노드(Parent Node): 자식 노드를 가지는 노드
✅ 자식 노드(Child Node): 부모 노드로부터 연결된 노드
✅ 형제 노드(Sibling Nodes): 같은 부모를 가지는 노드들
✅ 리프 노드(Leaf Node): 자식 노드가 없는 노드
✅ 깊이(Depth): 루트에서 특정 노드까지의 거리
✅ 높이(Height): 특정 노드에서 가장 깊은 리프 노드까지의 거리

---

🔹 트리의 주요 유형

1. 이진 트리(Binary Tree)

✅ 각 노드가 최대 두 개의 자식 노드를 가지는 트리

✔️ 이진 트리 예제 (Python):

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

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

    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert(self.root, data)

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

📌 이진 트리는 탐색 및 정렬에 유용하며, 이진 탐색 트리(BST)로 확장될 수 있습니다.

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

✅ 이진 트리의 한 종류로, 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 가짐

✔️ BST의 특징:

• 탐색, 삽입, 삭제 연산이 평균 O(log n) 시간 복잡도를 가짐
• 정렬된 데이터의 검색 속도가 빠름
• 균형이 맞지 않으면 성능이 저하될 수 있음

📌 이진 탐색 트리는 데이터베이스 및 검색 시스템에서 핵심적인 역할을 합니다.

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

✅ 모든 서브트리의 높이 차이가 일정 범위를 유지하는 트리

✔️ 대표적인 균형 이진 트리:

• AVL 트리: 삽입/삭제 후 균형을 유지하기 위해 회전 연산을 수행
• 레드-블랙 트리(Red-Black Tree): 색상을 이용하여 균형을 유지

📌 균형 이진 트리는 BST의 탐색 성능을 최적화하는 데 중요한 역할을 합니다.

4. 힙(Heap)

✅ 완전 이진 트리의 한 형태로, 부모 노드가 특정 순서를 유지하도록 구성됨

✔️ 힙의 유형:

• 최대 힙(Max Heap): 부모 노드의 값이 자식 노드보다 크거나 같음
• 최소 힙(Min Heap): 부모 노드의 값이 자식 노드보다 작거나 같음

📌 힙은 우선순위 큐(Priority Queue) 구현에 사용됩니다.

5. 트라이(Trie, Prefix Tree)

✅ 문자열 탐색 및 저장에 최적화된 트리

✔️ 트라이의 특징:

• 문자열 검색 속도가 빠름 (O(m), m은 문자열 길이)
• 자동 완성, 사전(Dictionary) 구현 등에 사용

📌 트라이는 검색 엔진 및 자연어 처리(NLP) 시스템에서 널리 사용됩니다.

---

🔹 트리 순회(Tree Traversal) 방법

✅ 전위 순회(Preorder): 루트 → 왼쪽 → 오른쪽
✅ 중위 순회(Inorder): 왼쪽 → 루트 → 오른쪽 (정렬된 데이터 반환)
✅ 후위 순회(Postorder): 왼쪽 → 오른쪽 → 루트
✅ 레벨 순회(Level Order): BFS를 사용하여 레벨별로 탐색

✔️ 중위 순회 예제 (Python):

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.data, end=" ")
        inorder_traversal(node.right)

📌 중위 순회는 이진 탐색 트리에서 정렬된 순서로 데이터를 출력하는 데 사용됩니다.

---

📌 결론

✅ 트리(Tree)는 계층적 데이터를 저장하고 탐색하는 데 적합한 비선형 데이터 구조입니다.
✅ 이진 트리, BST, AVL 트리, 힙, 트라이 등 다양한 유형이 존재하며, 각각의 사용 목적이 다릅니다.
✅ 탐색, 정렬, 데이터 저장 등의 성능을 향상시키기 위해 트리 구조를 적절히 활용해야 합니다.
✅ 트리 순회 알고리즘을 이해하고 활용하면 효율적인 데이터 검색 및 처리가 가능합니다.